作用

有时候 more niubi than kmp

比较两个区间的字符串是否一致就可以用

原理

将一个字符串看成一个P进制的数

对比时取子串可以直接相减得出

注意点：
1. 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
2. 冲突问题：通过巧妙设置P (131 或 13331) , Q (264)(264)的值，一般可以理解为不产生冲突。

模板

字符串哈希

#include<iostream>

using namespace std;

const int N = 100010;
const int P = 131;      //P == 131 || P == 13331 冲突最少

typedef unsigned long long Ull;     //超过2的64次方可以自动取模

int n,m;
Ull h[N],p[N];          //h是对应子串哈希值,p是对应P的倍数
char s[N];

//比较两个子串是否重合
Ull get(int l,int r){
    return h[r] - h[l - 1] * p[r - l + 1];   //abcde - abc * p * p = de
}

int main(){
    cin >> n >> m >> s + 1;

    //init()
    p[0] = 1;
    for(int i = 1;i <= n;i ++){
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i];
    }

    //输入查找对比区间
    while(m --){
        int a,b,c,d;
        cin >> a >> b >> c >> d;

        if(get(a,b) == get(c,d)) puts("Yes");
        else puts("No");
    }
}