Thuật toán xâu

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

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

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

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