《算法竞赛进阶指南》0x14Hash 简单字符串Hash

题目链接：https://www.acwing.com/problem/content/140/

O(N)时间复杂度，很高效；对64位自动溢出取模

代码：

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define maxn 1000020
#define P 131
char s[maxn];
unsigned long long  Hash[maxn],p[maxn];//对于64取模,自然溢出 
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    p[0]=1;//p^0
    for(int i=1;i<=n;i++){
        Hash[i]=Hash[i-1]*P+(s[i]-'0'+1);
        p[i]=p[i-1]*P;//p^i
    }
    int m;
    cin>>m;
    int l1,r1,l2,r2;
    while(m--){
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        unsigned long long  hash1=Hash[r1]-Hash[l1-1]*p[r1-l1+1];
        unsigned long long hash2=Hash[r2]-Hash[l2-1]*p[r2-l2+1];
        if(hash1==hash2)printf("Yes
");
        else printf("No
");
    }
}