考场上没秒的话多拿5分并不划算的样子。
思想其实很简单嘛。
要统计答案，求以每个位置开始和结束的AA串数量就好了。那么枚举AA中A的长度L，每L个字符设一个关键点，这样AA一定经过相邻的两个关键点。计算出相邻关键点的最长公共前后缀，把对应的位置区间加一下。
求lcp和lcs可以用后缀数组，也可以用hash。
UPD：UOJ上有人sxbk把原来的hash卡了，稍微改了下。其实base随机就没事了，然而BZOJ上并不能调用time(0)。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=30005;
const int p=1e9+93;
ll f[N][2],g[N][2];
bool jud(int i1,int j1,int i2,int j2){return f[j1][1]-f[i1][1]*g[j1-i1][1]==f[j2][1]-f[i2][1]*g[j2-i2][1]&&0==(f[j1][0]+(p-f[i1][0])*g[j1-i1][0]+p-f[j2][0]+f[i2][0]*g[j2-i2][0])%p;
}
char z[N];
int a[N],b[N];
int main(){g[0][0]=1;g[0][1]=1;for(int i=1;i<N;++i){g[i][0]=2003*g[i-1][0]%p;g[i][1]=2011*g[i-1][1];}int q;scanf("%d",&q);while(q--){scanf("%s",z+1);int n=strlen(z+1);for(int i=1;i<=n;++i){f[i][0]=(z[i]+2003*f[i-1][0])%p;f[i][1]=z[i]+2011*f[i-1][1];}fill_n(a+1,n,0);fill_n(b+1,n,0);for(int i=1;i<=n/2;++i)for(int j=1;j<=n-i;j+=i)if(z[j]==z[j+i]){int l=0,r=min(i,j);while(l!=r){int m=l+r+1>>1;if(jud(j-m,j,j+i-m,j+i))l=m;elser=m-1;}int u=j-l+1;l=0,r=min(i-1,n-j-i);while(l!=r){int m=l+r+1>>1;if(jud(j,j+m,j+i,j+i+m))l=m;elser=m-1;}int v=j+l+1;if(u+i<=v){++a[u];--a[v-i+1];++b[u+i*2-1];--b[v+i];}}ll s=0;for(int i=1;i<=n;++i){a[i]+=a[i-1];b[i]+=b[i-1];s+=a[i]*b[i-1];}printf("%lld\n",s);}
}