字符串前缀哈希

• 匹配字符串不一定要用kmp，有时候也要用到字符串哈希
• 在大多数情况下字符串hash可以替代kmp的作用并大大降低时间复杂度

步骤

• 预处理所有前缀哈希

• 如何来定义某个前缀的hash值？

• 把字符串看成p进制的数
• "ABCD" = 1*p^3 + 2*p^2 + 3*p^1 + 4*p^0 把abcd…z视为0~26，这样可以得到一个数字但较大，
  最后通过一个哈希函数（modQ一个较小的数），映射到0~Q-1中的一个数
• 通过h[r] - h[l] * p^(r-l+1) 算出子串的hash值
• 根据串的hash值进行判断是否相同。

作用

• 根据母串的哈希值可以快速求出子串的哈希值。

注意

• 一般情况下，不能将某一个字母映射成0，”A”、”AA”、”AAA” 都是对应十进制的0，映射到了同一个数
• 在字符串哈希中不考虑冲突的情况

• 经验：p取131/13331 、Q取2^64，99.9%不会出现冲突。

• 用unsigned long long （0~2^64-1)来存哈希值，就不用modQ了。

• ABCDE 与 ABC 的前三个字符值是一样，只差两位，
• h[r] - h[l] * p^(r-l+1)的理解：乘上 P^2把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。

C++ 代码

#include <iostream>

using namespace std;

typedef unsigned long long ULL;//用unsigned long long存储，利用溢出mod2^64

const int N = 100010, P = 131;//P进制

int n, m;
char str[N];
ULL p[N], h[N];//p数组储存p的第i次方，h数组储存字符串前缀和哈希值

ULL get(int l, int r){//获得子串的hash值
    return h[r] - h[l-1] * p[r - l + 1];
}

int main(){
    scanf("%d%d", &n, &m);
    scanf("%s", str+1);//从索引1开始储存字符串。令str[0] = 0;
    p[0] = 1;

    //预处理前缀和和p数组
    for(int i = 1; i <= n; i++){
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + str[i]; //str[i] 不能等于0，防止冲突；本题直接取ASCLL值
    }

    while(m--){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if(get(l1,r1) == get(l2,r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}