Thuật toán xâu

Wiki › Thuật toán

huunguyen · Last updated 8, Tháng 4, 2026, 15:20

String Hashing

So sánh 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;
}
auto get_hash=[&](int l,int r){
    return (h[r+1]-h[l]*pw[r-l+1]%MOD+MOD*2)%MOD;
};

KMP — $O (| t | + | p |)$

vector<int> kmp_search(string t, string p) {
    string s=p+"#"+t; int n=s.size();
    vector<int> fail(n,0);
    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;
    }
    vector<int> res; int m=p.size();
    for (int i=m+1; i<n; i++) if (fail[i]==(int)m) res.push_back(i-2*m);
    return res;
}

Z-function — $O (N)$

z[i] = độ dài tiền tố dài nhất của $s$ khớp với chuỗi tại $s [i]$ .

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: s = p+"#"+t, z[i]>=|p| là vị trí khớp

Trie

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;
}

Bảng so sánh

Thuật toán	Thời gian	Ứng dụng
Hashing	$O (N)$ build, $O (1)$ query	So sánh chuỗi con
KMP	$O (N + M)$	Tìm pattern trong text
Z-function	$O (N)$	Tìm pattern, period
Trie	$O (‖ s ‖)$	Từ điển, XOR max
Aho-Corasick	$O (\sum ‖ p_{i} ‖ + ‖ t e x t ‖)$	Tìm nhiều pattern đồng thời
Manacher	$O (N)$	Palindrome dài nhất
Suffix Array	$O (N \log N)$	Chuỗi con, LCS, so sánh từ điển
Palindrome Tree	$O (N)$	Tất cả palindrome con phân biệt

Child pages

Bình luận

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