哈希算法入门篇
两段字符串，判断它们是否相等，朴素解法是一个一个的判断，时间复制度较大。哈希算法把字符串转换成整数，这样时间复杂度从O(N)变成了O(1)。类似于二进制，用P进制将字符串装换成整数，为避免重复，一般认为P取131或者1331，使用unsigned long long 就可以，默认对结果模一个2^64，会有溢出的情况，但影响很小。（字符串默认都是小写字母,采用26进制）
例如 str=“abcd"
Hash(str)=
Hash数组存储字符串所有的前缀（憨憨小白不会打次方:p)
这里还可以用到简单的递归
Hash[i]=Hash[i-1]*P+s[i]-‘a’+1
对于字符串任意区间（L,R）
Hash[L–R]=Hash[R]-hash[L-1]*P^(R-L+1)
简单验证即可得到
例题链接
代码实现
#include
#include
#define base 131
char s[1000000];
typedef unsigned long long ULL;
ULL h[1000001],p[1000001];
ULL ans(int left,int right)
{
return h[right]-h[left-1]*p[right-left+1];
}
int main()
{
int N;
scanf("%s",s+1);
int n=strlen(s+1);
scanf("%d",&N);
p[0]=1;
for(int i=1;i<=n;i++)
{
h[i]=(h[i-1]*base)+(s[i]-'a')+1;
p[i]=p[i-1]*base;
}
while(N--)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(ans(l1,r1)==ans(l2,r2))
printf("Yes\n");
else
printf("No\n");
}
}
作者：I'ivresse
