Thuật toán xâu

Wiki › Thuật toán

huunguyen · Last updated 28, Tháng 3, 2026, 22:50

Hashing (Băm chuỗi)

Băm chuỗi giúp so sánh hai chuỗi con trong $O (1)$ sau $O (N)$ tiền xử lý.

const long long MOD = 1e9+7, BASE = 31;

string s;
int n = s.size();
vector<long long> h(n+1, 0), pw(n+1, 1);

for (int i = 0; i < n; i++) {
    h[i+1] = (h[i] * BASE + (s[i]-'a'+1)) % MOD;
    pw[i+1] = pw[i] * BASE % MOD;
}

// Hash của s[l..r]
auto get_hash = [&](int l, int r) {
    return (h[r+1] - h[l] * pw[r-l+1] % MOD + MOD*2) % MOD;
};

// So sánh hai chuỗi con: O(1)
bool equal = (get_hash(l1, r1) == get_hash(l2, r2));

KMP — Tìm kiếm chuỗi con

Tìm tất cả vị trí xuất hiện của pattern $p$ trong text $t$ — $O (| t | + | p |)$ .

vector<int> kmp_search(string t, string p) {
    string s = p + "#" + t;
    int n = s.size();
    vector<int> fail(n, 0);

    // Xây dựng failure function
    for (int i = 1; i < n; i++) {
        int j = fail[i-1];
        while (j > 0 && s[i] != s[j]) j = fail[j-1];
        if (s[i] == s[j]) j++;
        fail[i] = j;
    }

    // Tìm vị trí khớp
    vector<int> result;
    int m = p.size();
    for (int i = m+1; i < n; i++)
        if (fail[i] == m) result.push_back(i - 2*m);
    return result;
}

Z-function

z[i] = độ dài tiền tố dài nhất của $s$ khớp với chuỗi bắt đầu tại $s [i]$ — $O (N)$ .

vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n, 0);
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r-i, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]]) z[i]++;
        if (i+z[i] > r) { l = i; r = i+z[i]; }
    }
    return z;
}

// Tìm pattern p trong text t
string s = p + "#" + t;
auto z = z_function(s);
int m = p.size();
for (int i = m+1; i < (int)s.size(); i++)
    if (z[i] >= m) cout << i-m-1 << " ";  // vị trí khớp

Trie

Cây tiền tố lưu tập hợp các chuỗi — tra cứu theo prefix trong $O (| s |)$ .

struct Trie {
    int ch[26];
    bool end;
    Trie() : end(false) { fill(ch, ch+26, -1); }
};

vector<Trie> trie(1);

void insert(string& s) {
    int cur = 0;
    for (char c : s) {
        int x = c - 'a';
        if (trie[cur].ch[x] == -1) {
            trie[cur].ch[x] = trie.size();
            trie.push_back(Trie());
        }
        cur = trie[cur].ch[x];
    }
    trie[cur].end = true;
}

bool search(string& s) {
    int cur = 0;
    for (char c : s) {
        int x = c - 'a';
        if (trie[cur].ch[x] == -1) return false;
        cur = trie[cur].ch[x];
    }
    return trie[cur].end;
}

Bảng so sánh

Thuật toán	Thời gian	Ứng dụng
String Hashing	$O (N)$ build, $O (1)$ query	So sánh chuỗi con, palindrome
KMP	$O (N + M)$	Tìm pattern trong text
Z-function	$O (N)$	Tìm pattern, period
Trie	$O (‖ s ‖)$ mỗi thao tác	Từ điển, autocomplete, XOR max

Bình luận

Không có bình luận tại thời điểm này.