【CH1401】兔子与兔子

hash的入门题，通过hash我们可以在O(1)的时间里判断一个字符串的任意子串是否相等，恰好符合本题题意。

设计hash函数f[i]存储字符串s第1~i的子串的哈希值。显然存在f[i]=f[i-1]*131+(s[i]-'a'+1).

有了f数组，就可以求出任意子串的哈希值，因此我们就可以判断任意子串是否相等。

若要求字符串s的i~j的子串，即f[j]-f[i-1]*131^j-i+1。我们再预处理出131的整数次幂即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 char s[1000010];
 6 int f[1000010],p[1000010];
 7 int m,n;
 8 int main() {
 9     scanf("%s",s+1);
10     scanf("%d",&m);
11     n=strlen(s+1);
12     p[0]=1;
13     for(int i=1;i<=n;i++) {
14         f[i]=f[i-1]*131+(s[i]-'a'+1);
15         p[i]=p[i-1]*131;
16     }
17     while(m--) {
18         int l1,l2,r1,r2;
19         scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
20         if(f[r1]-f[l1-1]*p[r1-l1+1]==f[r2]-f[l2-1]*p[r2-l2+1]) puts("Yes");
21         else puts("No");
22     }
23     return 0;
24 }

AC Code