Skip to content
字符串

哈希

cpp
struct StrHash{
    int MOD,BASE,n;
    vector<int> p,h;
    StrHash(int n_=0){
        randing();
        init(n_);
    }
    StrHash(string s){
        randing();
        init(s.size());
        work(s);
    }
    void init(int n_){
        n=n_+1;
        p.assign(n, int{});
        h.assign(n, int{});
        p[0]=1;
        h[0]=0;
    }
    void randing(){
        srand(time(0));
        MOD = 998244353 + rand() % 10008;
        BASE = 33 + rand() % 234;
    }
    void work(string s){
        for(int i=1;i<n;i++){
            p[i] = ((long long)p[i - 1] * BASE) % MOD; 
            h[i]=((long long)h[i-1]*BASE+s[i-1]-'a')%MOD;
        }
    }
    int get(int l,int r){
        return (h[r] - (long long) h[l-1] * p[r-l+1] % MOD + MOD) % MOD;
    }
};

KMP

cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int pmt[MAXN];
void get_pmt(const string& s) {
    for (int i = 1, j = 0; i < s.length(); ++i) {
        while (j && s[i] != s[j]) j = pmt[j - 1];
        if (s[i] == s[j]) j++;
        pmt[i] = j;
    }
}
void kmp(const string& s, const string& p) {
    for (int i = 0, j = 0; i < s.length(); ++i) {
        while (j && s[i] != p[j]) j = pmt[j - 1];
        if (s[i] == p[j]) j++;
        if (j == p.length()) {
            cout << i - j + 2 << '\n'; // 因为要1-index,所以是+2
            j = pmt[j - 1];
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    string s, p;
    cin >> s >> p;
    get_pi(p);
    kmp(s, p);
    for (int i = 0; i < p.length(); ++i)
        cout << pmt[i] << ' ';
    return 0;
}

最小表示法

cpp
int n=read();
int a[n*2];
For(i,0,n){
    a[i]=read();
    a[i+n]=a[i];
}
int i=0,j=1,k=0;
while(i<n&&j<n){
    while(a[i+k]==a[j+k])k++;
    if(a[i+k]>a[j+k])i+=k+1;
    else j+=k+1;
    k=0;
    if(i==j)j++;
}
int st=min(i,j);
For(i,st,st+n){
    char f=' ';
    if(i==st+n-1)f=endl;
    cout<<a[i]<<f;
}

字典树

cpp
const int N=3e5+5;
int nxt[N][26][2];
int cnt = 0;
string s;
For(i, 0, n)
{   
    cin >> s;
    int cur = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int c = s[i] - 'a';
        if (!nxt[cur][c][0])
        {
            nxt[cur][c][0] = ++cnt;
        }
        nxt[cur][c][1]++;
        cur = nxt[cur][c][0];
    }
}

Z函数

cpp
std::vector<int> zFunction(std::string s) {
    int n = s.size();
    std::vector<int> z(n + 1);
    z[0] = n;
    for (int i = 1, j = 1; i < n; i++) {
        z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > j + z[j]) {
            j = i;
        }
    }
    return z;
}