字符串前缀哈希法

前面为acwing上课截图！

总结：字符串前缀哈希，每一个字符看成进制位，然后转换成十进制取模。

l~r的哈希值：h[r]-h[l-1]*p[r-l+1];

841、字符串哈希 - AcWing题库

#includeusing namespace std;typedef unsigned long long ULL;const int P=131,N=1e5+10;//取模Pchar str[N];ULL h[N],p[N];//h[]哈希表 p[]进制位int n,m;ULL get(int l,int r)//得到l~r的哈希值{return h[r]-h[l-1]*p[r-l+1];}int main(){scanf("%d%d",&n,&m);scanf("%s",str+1);p[0]=1;//进制 p^0=1for(int i=1;i<=n;i++){p[i]=p[i-1]*P;//进制每次加一h[i]=h[i-1]*P+str[i];//哈希值由前一个×进制+本字符值}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;}