缺点：多重哈希容易卡常，单哈希容易被hack

#define ll long long
const ll MOD = 998244353, BASE = 171;
int n = s.size();
vector<ll> H(n+1, 0), B(n+1, 1);
// string s[] index from 0 to n-1
// B[i] = BASE^i
// s[i...j] = s[0...j] - s[0...i-1]
// hash s[0...i-1] = H[i] = s[0]*B[i-1]+s[1]*B[i-2]+...+s[i-1]*B[0]
// hash s[0...j] = H[j+1] = s[0]*B[j]+s[1]*B[j-1]+...+s[j]*B[0]
// hash s[i...j] = H[j+1] - H[i]*B[j-i+1]
// hash s[i...j-1] = H[j] - H[i]*B[j-i]
for (int i=1; i<=n; i++) {
    H[i] = (H[i-1]*BASE%MOD + s[i-1])%MOD;
}
for (int i=1; i<=n; i++) {
    B[i] = B[i-1]*BASE%MOD;
}
auto hash = [&](int l, int r) {  // hash of s[l...r-1]
    return (H[r] - H[l] * B[r - l] % MOD + MOD) % MOD;
};

对于长度为n的字符串s，下标从0开始。

令$B[i] = BASE^i$

长度为i的前缀子串s[0…i-1]的哈希值, $H[i] = \sum \limits_{j=0}^{i-1} s[j]*B[i-1-j]$

长度为len的子串s[i…j]的哈希值H[j+1] - H[i]*B[j-i+1] 注意取模。

毒瘤写法，自然溢出

#define ull unsigned long long
#define BASE 131
int main() {
    string s = "abcdabcdab";
    int n = s.size();//n=10
    vector<ull> H(n+1, 0), B(n+1, 1);
    for (int i=1; i<=n; i++) {
        H[i] = H[i-1]*BASE+s[i-1];
        B[i] = B[i-1]*BASE;
    }
		// string s[] index from 0 to n-1
    // H[i] 前i个字符的前缀串哈希值, H[0] = 0。
		// B[i] = BASE^i
    // H[r]-H[l]*B[r-l] = s[l...r-1]
    // s[l...r] = H[r+1] - H[l]*B[r-l+1]
    auto hash = [&](int l, int r) {  // hash of s[l...r-1]
        return H[r] - H[l] * B[r - l];
    };
		cout << H[3] - H[0]*B[3] << " " << H[7] - H[4]*B[3] << endl; // abc abc
    cout << H[4] - H[0]*B[4] << " " << H[8] - H[4]*B[4] << endl; // abcd abcd
    cout << H[2] - H[0]*B[2] << " " << H[6] - H[4]*B[2] << " " << H[10]-H[8]*B[2] << endl; // abcd abcd
    return 0;
}
/*
1677554 1677554
219759674 219759674
12805 12805 12805
*/

应用

多重哈希

// 单哈希容易被卡，封装用多重哈希
// 两个串的哈希相等，说明串大概率相等。
struct SHash {
#define ll unsigned long long
    // string s[] index from 0 to n-1
    // B[i] = BASE^i
    // s[i...j] = s[0...j] - s[0...i-1]
    // hash s[0...i-1] = H[i] = s[0]*B[i-1]+s[1]*B[i-2]+...+s[i-1]*B[0]
    // hash s[0...j] = H[j+1] = s[0]*B[j]+s[1]*B[j-1]+...+s[j]*B[0]
    // hash s[i...j] = H[j+1] - H[i]*B[j-i+1]
    // hash s[i...j-1] = H[j] - H[i]*B[j-i]
    vector<ll> H, B;
    ll len, base, mod;
    SHash(string& s, ll base = 171, ll mod = 998244353)
        : H(s.size() + 1, 0),
          B(s.size() + 1, 1),
          len(s.size()),
          base(base),
          mod(mod) {
        for (int i = 1; i <= len; i++) {
            H[i] = (H[i - 1] * base % mod + s[i - 1]) % mod;
            B[i] = B[i - 1] * base % mod;
        }
    }
    ll hash(int l, int r) {  // hash of s[l...r-1]
        return (H[r] - H[l] * B[r - l] % mod + mod) % mod;
    };
};
// 167772161,469762049,754974721,998244353,1045430273,1051721729,1053818881,1000000007
struct MSHash{
    vector<SHash> h;
    MSHash(string& s) {
        // MOD 太大会溢出
        vector<pair<ll, ll>> param = {{137, 167772161},
																				{139, 469762049},
																				{149, 754974721},
																				{167, 998244353},
																				{151, 1045430273},
																				{157, 1051721729},
																				{163, 1053818881},
																				{173, 1000000007}};
        for (auto [i, j] : param) {
            h.emplace_back(s, i, j);
        }
    }
    // is s[l1...r1-1] == s[l2...r2-1] ? s[] index from 0
    bool check(int l1, int r1, int l2, int r2) {
        for (auto& i : h) {
            if (i.hash(l1, r1) != i.hash(l2, r2))
                return false;
        }
        return true;
    }
};

实际解题时封装太多层还是容易超时，建议用两个哈希

SHash h1(s), h2(s, 173, 1000000007);
// 检测 s[a,b) == s[c,d)
h1.hash(a, b) == h1.hash(c, d) && h2.hash(a, b) == h2.hash(c, d)

实战还是别用结构体封装，太容易卡常了

再写一个常数较小的双重哈希

#define N 500005
#define ll long long
const ll MOD1 = 998244353, BASE1 = 251;
const ll MOD2 = 1073676287, BASE2 = 211;
ll H1[N], H2[N], B1[N], B2[N];

void init(string& s) {
    int n = s.size();
    H1[0] = H2[0] = 0;
    B1[0] = B2[0] = 1;
    for (int i=1; i<=n; i++) {
        H1[i] = (H1[i-1]*BASE1%MOD1 + s[i-1])%MOD1;
        B1[i] = B1[i-1]*BASE1%MOD1;
        H2[i] = (H2[i-1]*BASE2%MOD2 + s[i-1])%MOD2;
        B2[i] = B2[i-1]*BASE2%MOD2;
    }
}
ll hash1(int l, int r) {  // hash of s[l...r-1]
    return (H1[r] - H1[l] * B1[r - l] % MOD1 + MOD1) % MOD1;
};
ll hash2(int l, int r) {  // hash of s[l...r-1]
    return (H2[r] - H2[l] * B2[r - l] % MOD2 + MOD2) % MOD2;
};
bool check(int l1, int r1, int l2, int r2) {
    return hash1(l1, r1) == hash1(l2, r2) && hash2(l1, r1) == hash2(l2, r2);
}

滚动哈希

#define ll long long

/*
    滚动哈希,窗口大小为n
    当前字符串长度为len, hash = s[0]*BASE^{len-1} + s[1]*BASE^{len-2} + ... + s[len-1]*BASE^{0}
    左边移除s[0], hash -= s[0]*BASE^{len-1}
    右边添加ch, hash =  hash*BASE + ch
*/ 
template<typename T>
struct SlideStr {
    ll hash = 0, n, mod, base;
    queue<T> q;
    vector<ll> B;
    SlideStr(ll n, ll mod = 998244353, ll base = 173): n(n), mod(mod), base(base), B(n+1) {
        B[0] = 1;
        for (int i = 1; i <= n; i++) 
            B[i] = B[i - 1] * base % mod;
    }
    bool del_l() {
        int len = q.size();
        if (len == 0) return false;
        hash = (hash - q.front()*B[len-1]%mod + mod)%mod;
        q.pop();
        return true;
    }
    bool add_r(T ch) {
        if (q.size() == n) return false;
        q.push(ch);
        hash = (hash*base%mod+ch)%mod;
        return true;
    }
    ll get_hash() {
        return hash;
    }
};