https://www.lydsy.com/JudgeOnline/problem.php?id=4650
如果能够预处理出
suf[i] 以i结尾的形式为AA的子串个数
pre[i] 以i开头的形式为AA的子串个数
ans= ∑ suf[i]*pre[i+1]
这两个数组的求法，类似bzoj 2119、3238
枚举|A|的长度len，将序列每len个分一块，取每块内第一个元素作为关键点
每个合法的AA恰好占据两个关键点
枚举每一个关键点i，取j=i+len
计算[i,n]和[j,n]的lcp，[1,i]和[1,j]的lcs（通过原串和反串的后缀数组）
假设以i为基准，lcp向后匹配的最远点为r，lcs向前匹配的最远点为l
令cnt=r-l+1 - len + 1
那么AA的开头可以是[l，r]内任意长度为len的子串,这种子串有cnt个，即pre[l,l+cnt-1] 都会加一个贡献
假设以j为基准，lcp向后匹配的最远点为r，lcs向前匹配的最远点为l
令cnt=r-l+1 - len + 1
那么AA的结尾可以是[l，r]内任意长度为len的子串,这种子串有cnt个，即pre[r,r-cnt+1] 都会加一个贡献
利用差分累计贡献
注意：
用 后缀数组，有多组数据时，除了统计数量用的v数组要清零，rank数组也要清零
后面+k 使rank 使用超过n的rank，超过n的rank存储的时上一组数据的rank
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> #define N 30002 using namespace std; int n;
char s[N]; int pre[N],suf[N]; int Log[N]; struct SA
{
int a[N];
int sa[][N],rk[][N];
int v[N];
int p,q;
int k;
int height[N];
int st[N][]; void mul(int *sa,int *rk,int *SA,int *RK)
{
for(int i=;i<=n;++i) v[rk[sa[i]]]=i;
for(int i=n;i;--i) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k;
for(int i=n-k+;i<=n;++i) SA[v[rk[i]]--]=i;
for(int i=;i<=n;++i) RK[SA[i]]=RK[SA[i-]]+(rk[SA[i]]!=rk[SA[i-]] || rk[SA[i]+k]!=rk[SA[i-]+k]);
} void pre_sa()
{
p=; q=;
memset(v,,sizeof(v));
memset(rk,,sizeof(rk));
for(int i=;i<=n;++i) v[a[i]]++;
for(int i=;i<=;++i) v[i]+=v[i-];
for(int i=;i<=n;++i) sa[p][v[a[i]]--]=i;
for(int i=;i<=n;++i) rk[p][sa[p][i]]=rk[p][sa[p][i-]]+(a[sa[p][i]]!=a[sa[p][i-]]);
for(k=;k<n;k<<=,swap(p,q)) mul(sa[p],rk[p],sa[q],rk[q]);
} void pre_height()
{
int j,k=;
for(int i=;i<=n;++i)
{
j=sa[p][rk[p][i]-];
while(a[i+k]==a[j+k]) k++;
height[rk[p][i]]=k;
if(k) k--;
}
} void pre_st()
{
memset(st,,sizeof(st));
for(int i=;i<=n;++i) st[i][]=height[i];
for(int j=,k=;j<=;++j,k<<=)
for(int i=;i+k*-<=n;++i)
st[i][j]=min(st[i][j-],st[i+k][j-]);
} void pre()
{
pre_sa();
pre_height();
pre_st();
} int get(int i,int j)
{
i=rk[p][i]; j=rk[p][j];
if(i>j) swap(i,j);
i++;
int l=Log[j-i+];
return min(st[i][l],st[j-(<<l)+][l]);
}
};
SA SA1,SA2; void solve()
{
memset(pre,,sizeof(pre));
memset(suf,,sizeof(suf));
int j;
int lcp,lcs;
int cnt=;
for(int len=;len<n;++len)
{
for(int i=len;i+len<=n;i+=len)
{
j=i+len;
lcp=SA1.get(i,j);
if(lcp>len) lcp=len;
lcs=SA2.get(n-i+,n-j+);
if(lcs>len) lcs=len;
if(lcp+lcs->=len)
{
suf[j+len-lcs]++;
suf[j+lcp]--;
pre[i-lcs+]++;
pre[i+lcp-len+]--;
}
}
}
for(int i=;i<=n;++i) pre[i]+=pre[i-],suf[i]+=suf[i-];
long long ans=;
for(int i=;i<=n-;++i) ans+=1LL*suf[i]*pre[i+];
cout<<ans<<'\n';
} int main()
{
//freopen("testdata.in","r",stdin);
//freopen("__.txt","w",stdout);
int T;
scanf("%d",&T);
for(int i=;i<N;++i) Log[i]=Log[i>>]+;
while(T--)
{
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;++i) SA1.a[i]=s[i]-'a'+;
memcpy(SA2.a,SA1.a,sizeof(SA2.a));
reverse(SA2.a+,SA2.a+n+);
SA1.a[n+]=SA2.a[n+]=;
SA1.pre();
SA2.pre();
solve();
}
}