跳转至

字符串哈希

参考代码
const ll mod[2] = { 2000000011, 3000000019};
struct Hash{
    int size, base[2] = {  20023,20011 };
    vector<array<ll, 2>> hash, pow_base;
    Hash(){}
    Hash(const string& s){
        size = s.size();
        hash.resize(size);
        pow_base.resize(size);
        pow_base[0][0] = pow_base[0][1] = 1;
        hash[0][0] = hash[0][1] = s[0];
        for(int i = 1; i < size; i++){
            hash[i][0] = (hash[i - 1][0] * base[0] + s[i]) % mod[0];
            hash[i][1] = (hash[i - 1][1] * base[1] + s[i]) % mod[1];
            pow_base[i][0] = pow_base[i - 1][0] * base[0] % mod[0];
            pow_base[i][1] = pow_base[i - 1][1] * base[1] % mod[1];
        }
    }
    array<ll, 2> operator[](const array<int, 2>& range)const{
        if(range[0] == 0)return hash[range[1]];
        return { (hash[range[1]][0] - hash[range[0] - 1][0] * pow_base[range[1] - range[0] + 1][0] % mod[0] + mod[0]) % mod[0], (hash[range[1]][1] - hash[range[0] - 1][1] * pow_base[range[1] - range[0] + 1][1] % mod[1] + mod[1]) % mod[1] };
    }
};

具体使用

P3375 【模板】KMP字符串匹配

\(S\) 初始化 \(Hash\ hash(S)\)

\(hash[\{l,r\}]\)就是 \(S_{l \sim r}\) 的哈希值

参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod[2] = { 2000000011, 3000000019};
struct Hash{
    int size, base[2] = {  20023,20011 };
    vector<array<ll, 2>> hash, pow_base;
    Hash(){}
    Hash(const string& s){
        size = s.size();
        hash.resize(size);
        pow_base.resize(size);
        pow_base[0][0] = pow_base[0][1] = 1;
        hash[0][0] = hash[0][1] = s[0];
        for(int i = 1; i < size; i++){
            hash[i][0] = (hash[i - 1][0] * base[0] + s[i]) % mod[0];
            hash[i][1] = (hash[i - 1][1] * base[1] + s[i]) % mod[1];
            pow_base[i][0] = pow_base[i - 1][0] * base[0] % mod[0];
            pow_base[i][1] = pow_base[i - 1][1] * base[1] % mod[1];
        }
    }
    array<ll, 2> operator[](const array<int, 2>& range)const{
        if(range[0] == 0)return hash[range[1]];
        return { (hash[range[1]][0] - hash[range[0] - 1][0] * pow_base[range[1] - range[0] + 1][0] % mod[0] + mod[0]) % mod[0], (hash[range[1]][1] - hash[range[0] - 1][1] * pow_base[range[1] - range[0] + 1][1] % mod[1] + mod[1]) % mod[1] };
    }
};
void solve(){
    string A, B;
    cin >> A >> B;

    Hash hash_A(A), hash_B(B);
    for(int i = 0; i + B.size() - 1 < A.size(); i++){
        if(hash_A[{i, i + (int)B.size() - 1}] == hash_B[{0, (int)B.size() - 1}]){
            cout << i + 1 << "\n";
        }
    }
    vector<int> next(B.size(), -1);
    for(int i = 1, j = -1; i < B.size(); i++){
        while(j >= 0 && B[i] != B[j + 1])j = next[j];
        if(B[i] == B[j + 1])j++;
        next[i] = j;
    }
    for(auto& i : next)i++;
    for(auto& i : next)cout << i << " ";
    cout << "\n";
}
int main(){
#ifdef DEBUG
    double start = clock();
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--)solve();
#ifdef DEBUG
    cout << fixed << setprecision(6);
    cout << (clock() - start) / CLOCKS_PER_SEC << "\n";
#endif
}