字符串哈希

分析

1. 快速判断两个字符串是否相等，就用字符串哈希这个算法，模板参考acwing的：数据结构算法模板；
2. 这个算法的思想就是将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低；
3. h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64 ，取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果；
4. get函数就是获取r到l这段子串的哈希值，采用 h[r] - h[l - 1] * p[r - l + 1]（乘一个p^r-l+1，相当于移位）；
5. 预处理：将字符串前面加一个空格，使索引从1开始，p[i] = p[i - 1] * P;（处理存储p的 i 次幂的数组）,h[i] = h[i - 1] * P + s[i];（计算前k个字母的哈希值）；
6. 关于此题的区间判断，画一个图；
   

#include 

using namespace std;

typedef unsigned long long ULL;
const int N = 2e+6 + 10;
//h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
ULL h[N], p[N];
int n, P = 131;
ULL ans = 1;
string s;

ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    cin.tie(0);
    cin >> n >> s;
    s = " " + s;
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i];
    }
    for (int k = 1; k < n; ++k) {
        if (get(k + 1, n) == get(1, n - k) && get(1, k) == get(n - k + 1, n))
            ans++;
    }
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33