先上代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1000005;
char a[N];
ll p[N],q,n,ans=0,now=1;
void pre(){
	p[1]=0;
	int j=0;
	for(int i=1;i<n;i++){
		while(j>0 && a[j+1]!=a[i+1]) j=p[j];
		if(a[j+1]==a[i+1]) j++;
		p[i+1]=j;
	}
}
void dd(int *d){
	for(int i=1;i<=n;i++) printf("%2.d ",d[i]);
	printf("\n");
}
int main(){
	scanf("%lld",&n);
	scanf("%s",a+1);
	pre();
	for(int i=1;i<=n;i++){
		if(!p[i]) continue;
		if(a[i]==a[now]){now=i;q=i-1;}
		ans+=q;
	}
	//dd(p);dd(q);
	printf("%lld\n",ans);
	return 0;
} 

这个我是打了好多的表找到的规律自以为，然后愉快的只有40pt。

先用now指针指向a1，

如果找到和a1相同的元素就更新前缀值并且加上；

如果不相同就看pi是不是0，

是0就不做变动（A必定不是QQ的前缀）；不是0咱们就把修改now指针时记录下来的值加到答案上。

我想知道我为什么错了，或者一组可以证伪的数据也行。蟹蟹