C++是实现字符串哈希

关于字符串哈希：

其中需要主义的一个小地方：

字符串前缀哈希的题目：

代码实现：

1.  
   // 字符串前缀哈希法：
2.  
   #include <iostream>
3.  
   #include <algorithm>
4.  
   using namespace std;
5.  
    
6.  
   // 把字符串看成是一个 P 进制数，每个字符的 ASCII 码对应数的一位
7.  
   // ASCII 范围 0 - 127，最少 128 进制，经验上取 131 或 13331 冲突率低
8.  
   const int N = 100010, P = 131;
9.  
   typedef unsigned long long ULL;
10.  
     
11.  
    //str存的是字符串
12.  
    //h[N]存的是字符串的映射值，h[i] 对应数组的前i个元素的映射值
13.  
    //p[N]存的是加权
14.  
    char str[N];
15.  
    ULL h[N], p[N];
16.  
     
17.  
    ULL get(int l, int r)
18.  
    {
19.  
    return h[r] - h[l - 1]*p[r - l 1];
20.  
    }
21.  
     
22.  
    int main()
23.  
    {
24.  
    int n = 0, m = 0;
25.  
    scanf("%d%d", &n, &m);
26.  
    scanf("%s", str 1); //对应下面的前缀和，下标从1开始
27.  
     
28.  
     
29.  
    p[0] = 1;
30.  
    for(int i = 1; i <= n; i )
31.  
    {
32.  
    h[i] = h[i - 1] * P str[i];
33.  
    p[i] = p[i - 1] * P; //对应公式
34.  
    }
35.  
     
36.  
    while(m--)
37.  
    {
38.  
    int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
39.  
    scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
40.  
     
41.  
    if(get(l1, r1) == get(l2, r2)) puts("Yes");
42.  
    else puts("No");
43.  
    }
44.  
    return 0;
45.  
    }

写在最后，一些补充的地方：

1. 补充一点，在C 中int溢出是undefined behavior,是否会取模取决于编译器。unsigned int溢出是define behavior，在溢出时会自动取模

2. 把字符串看成是一个 P 进制数，每个字符的 ASCII 码对应数的一位
3. ASCII 范围 0 - 127，最少 128 进制，经验上取 131 或 13331 冲突率低
4. 字符串很长，对应的数太大，通过模 2^64 把它映射到 [0, 2^64 - 1]
5. 用 unsigned long long 存储，溢出相当于对 2^64 取模，省略了手动运算，该方法的好处是，可以利用前缀哈希直接求出子串哈希（减去高位）

这篇好文章是转载于：学新通技术网