2.字符串哈希

把字符串看成是 p 进制的数字。字符串左边表示数字的高位，最低位是数字的最右边，最低位是 p^0 ，次低位是 p^1 ，哈希可以通过取模来实现。哈希实际上是进行了一次映射操作，把大数据范围缩小到一个比较小的可以接受的范围。p = 131 or 13331 ,q = 2^64 , 大概率不会出现冲突。q 表示取模的数字。相当于要模拟一个 p 进制的减法。unsigned long long is $0-2^{64}-1$ 。实际上考试的时候，除非遇到这个原题，不然我感觉我应该写不出来。把字符串理解为 131 进制的数字，然后把两个数字对齐（通过乘以某个数字实现），比较两个数字的哈希值是否相等来判断这两个字符串是否相等。实在是太巧妙了。

#include<algorithm>
#include<cstring>
#include<iostream>using namespace std;typedef unsigned long long ULL;
const int N=100010;ULL h[N];
ULL p[N];
int k=131;
char str[N];ULL get(int l,int r){return h[r]-h[l-1]*p[r-l+1];
}int main(){int n,m;cin>>n>>m;cin>>str+1;p[0]=1;for(int i=1;i<=n;i++){p[i]=p[i-1]*k;h[i]=h[i-1]*k+str[i];}while(m--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;if(get(l1,r1)==get(l2,r2)){puts("Yes");}else{puts("No");}}return 0;
}