Tìm kiếm lặp lại trên cùng một văn bản (C++)

Khi cần tìm kiếm một mẫu (pattern) nhiều lần trên cùng một văn bản tĩnh (ví dụ: tìm kiếm trong Bible, từ điển, log lớn), việc quét tuyến tính O(n) mỗi lần là chậm. Giải pháp: xây dựng **cấu trúc chỉ mục (index)** một lần, sau đó truy vấn nhanh.

Các cấu trúc chỉ mục phổ biến

Ví dụ đơn giản: Naive Search (baseline)

Code dưới đây minh họa tìm kiếm đơn giản — không phải cấu trúc chỉ mục, chỉ để so sánh.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector naiveSearch(const string& text, const string& pattern) {
    vector positions;
    int n = text.size(), m = pattern.size();
    if (m == 0 || n < m) return positions;
    
    for (int i = 0; i <= n - m; ++i) {
        bool match = true;
        for (int j = 0; j < m; ++j) {
            if (text[i+j] != pattern[j]) { match = false; break; }
        }
        if (match) positions.push_back(i);
    }
    return positions;
}

int main() {
    string text = "thisistutorialspointthisisacppprogram";
    string pattern = "is";
    
    auto pos = naiveSearch(text, pattern);
    cout << "Pattern '" << pattern << "' found at positions: ";
    for (int p : pos) cout << p << ' ';
    cout << "\nTotal: " << pos.size() << " occurrences\n";
    return 0;
}

Kết quả

Pattern 'is' found at positions: 2 4 23 25
Total: 4 occurrences

Cải tiến: Suffix Array (tìm kiếm O(m log n))

// Xây dựng Suffix Array đơn giản (O(n log^2 n) - đủ cho demo)
vector buildSuffixArray(const string& s) {
    int n = s.size();
    vector sa(n), rank(n), tmp(n);
    for (int i = 0; i < n; ++i) { sa[i] = i; rank[i] = s[i]; }
    
    for (int k = 1; k < n; k <<= 1) {
        auto cmp = [&](int i, int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            int ri = i + k < n ? rank[i+k] : -1;
            int rj = j + k < n ? rank[j+k] : -1;
            return ri < rj;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; ++i)
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
        rank = tmp;
        if (rank[sa[n-1]] == n-1) break;
    }
    return sa;
}

// Tìm kiếm nhị phân trên Suffix Array
vector searchSA(const string& text, const string& pat, const vector& sa) {
    int n = text.size(), m = pat.size();
    int l = 0, r = n - 1, first = -1;
    // Lower bound
    while (l <= r) {
        int mid = (l + r) / 2;
        if (text.compare(sa[mid], m, pat) >= 0) { first = mid; r = mid - 1; }
        else l = mid + 1;
    }
    if (first == -1 || text.compare(sa[first], m, pat) != 0) return {};
    
    l = first; r = n - 1; int last = first;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (text.compare(sa[mid], m, pat) <= 0) { last = mid; l = mid + 1; }
        else r = mid - 1;
    }
    vector res;
    for (int i = first; i <= last; ++i) res.push_back(sa[i]);
    sort(res.begin(), res.end());
    return res;
}

So sánh hiệu năng (độ dài text ~ 10^6)

Naive search (mỗi query):     ~10-100 ms
Suffix Array build (1 lần):   ~200-500 ms
Suffix Array query:           ~0.01-0.1 ms (log n)
Speedup:                      100x - 1000x

Thư viện thực tế

• SeqAn (C++): Suffix Array, FM-Index, Bioinformatics.
• SDSL (Succinct Data Structure Library): nén Suffix Array/Tree.
• StringZilla: SIMD-accelerated string search.
• Lucene/Elasticsearch (Java): Inverted index cho full-text search.

Kết luận

• Ít truy vấn / text nhỏ: Naive / KMP / Boyer-Moore đủ dùng.
• Nhiều truy vấn trên text tĩnh lớn: Xây **Suffix Array** hoặc **Inverted Index** (nếu tìm từ).
• Tìm nhiều pattern cùng lúc: **Aho-Corasick**.
• Cần đếm/substring phức tạp: **Suffix Automaton**.

Việc chọn cấu trúc dữ liệu phù hợp là chìa khóa cho hệ thống tìm kiếm hiệu năng cao.