https://vjudge.net/problem/Gym-103428D
题意：
给你一个字符串，q次查询，每次查询会将字符串中的一个字符修改为#，求在新串中可以选出几种长度不同的前后缀，使得前后缀相同
分析：
对于长度为n的串，#在pos位置时，只需对长度小于等于min(pos-1,n-pos)的前后缀查询即可
q在1e6 故要先预处理主串看看有哪些长度的前后缀是相同的 再O(1)查询
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N];
int n;
int ne[N],ans[N];
void getne(){
ne[0]=-1;
int i=0,j=-1;
while(i<n){
if(j==-1|| s[i]==s[j]){
i++,j++;
ne[i]=j;
}
else j=ne[j];
}
}
void getans(){
getne();
int now=ne[n];
while(now){
ans[now]++;
now=ne[now];
}
//需要注意的是，只需要遍历到中间位置，后半部分和前面其对称位置的答案是一样的。
//而遍历到后半位置就会错误，按照题目要求，公共前后缀不可能超过一半。
for(int i=1;i<=n/2;i++){
ans[i]+=ans[i-1];
}
}
signed main()
{
scanf("%s",s);
n=strlen(s);
getans();
int m;cin>>m;
while(m--){
int k;scanf("%d",&k);
k=min(k-1,n-k);
printf("%d\n",ans[k]);
}
return 0;
}
————————————————
版权声明：本文为CSDN博主「chmpy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_55032066/article/details/121685812