字符串哈希 + 倍增$(89ms)$
枚举所有后缀,哈希 + 倍增判断该后缀与字符串B重合的位数
然后装入桶里,$O(1)$回答所有问题
跑得比y总的代码还快
#include<cstdio>
#include<algorithm>
using namespace std;
#define reg register
#define ll long long
#define ull unsigned long long
const int N = 2e5 + 10;
char str1[N];
char str2[N];
int pi[N];
int len1,len2,q;
ull ha1[N];
ull ha2[N];
ull k[N];
int find(int);
bool check(int,int);
int main()
{
scanf("%d%d%d",&len1,&len2,&q);
scanf("%s%s", str1 + 1, str2 + 1);
k[0] = 1;
for (reg int i = 1; i <= len1; ++i){
ha1[i] = ha1[i - 1] * 131 + str1[i];//求A串哈希
k[i] = k[i - 1] * 131;//打次方表
}
for (reg int i = 1; i <= len2; ++i){
ha2[i] = ha2[i - 1] * 131 + str2[i];//求B串哈希
}
for (reg int i = 1; i <= len1; ++i){
++pi[find(i)];//枚举每个后缀,离线求出所有答案
}
reg int x;
while (q--){
scanf("%d",&x);
printf("%d\n",pi[x]);//对于每个问题进行回答
}
return 0;
}
int find(int x)//倍增部分
{
int k = 1,i = 0;
while (k){
if (check(x,i + k)){
i += k;
k <<= 1;
}
else{
k >>= 1;
}
}
return i;
}
bool check(int x,int len)//check函数使用哈希判断字符串相等
{
return ha2[len] == (ha1[x + len - 1] - ha1[x - 1] * k[len]);
}