「优秀的拆分」可以说是非常优秀了
温馨提示：后缀数组多测要清空$tp$数组！！！！
设$st[i]$为以第$i$个字符为开头，能有多少个$AA$串；$en[i]$即以第$i$个字符为结尾，有多少个$AA$串。
答案就是$\sum\limits_{i=1}^{n-1}en[i]*st[i+1]$。我们就能用哈希（蒟蒻不会哈希只能强上$SA$）$O(n^2)$得到$95$分的好成绩。
（如果蒟蒻比赛写到这就懒得继续写了，散了散了）
枚举每个$A$串长度$len$，对母串每$len$个字符打一个标记，显然一个$AA$串一定覆盖两个标记。那么对于每两个相邻的标记，若它们的$LCS+LCP\ge len$就能产生$AA$串。（$LCS$是前缀的最长公共后缀，$LCP$是后缀的最长公共前缀）
并且这个$AA$串左右端点可以移动，移动范围为$LCS+LCP-len$，给这段区间$+1$，上差分。
时间复杂度$O(\sum\limits_{i=1}^{n}\frac{n}{i})=O(n\log n)$
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 30005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int lg[maxn],n,m;
long long st[maxn],en[maxn];
struct Suffix_Array{
int sa[maxn],rk[maxn],tp[maxn],tax[maxn],hei[maxn],f[maxn][25];
char s[maxn];
void Rsort(){
for(register int i=0;i<=m;++i)tax[i]=0;
for(register int i=1;i<=n;++i)++tax[rk[i]];
for(register int i=1;i<=m;++i)tax[i]+=tax[i-1];
for(register int i=n;i;--i)sa[tax[rk[tp[i]]]--]=tp[i];
}
void Ssort(){
for(register int i=1;i<=n;++i)rk[i]=s[i],tp[i]=i;
m=225,Rsort();
for(register int k=1,p=0;p<n;m=p,k<<=1){
p=0;
for(register int i=1;i<=k;++i)tp[++p]=n-k+i;
for(register int i=1;i<=n;++i)if(sa[i]>k)tp[++p]=sa[i]-k;
Rsort();
for(register int i=1;i<=n;++i)tp[i]=rk[i];
rk[sa[1]]=p=1;
for(register int i=2;i<=n;++i)
rk[sa[i]]=tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k]?p:++p;
}
}
void get_height(){
int k=0,x;
for(register int i=1;i<=n;++i){
if(rk[i]==1)continue;
if(k)--k;
x=sa[rk[i]-1];
while(i+k<=n&&x+k<=n&&s[i+k]==s[x+k])++k;
hei[rk[i]]=k;
}
}
void ST(){
for(register int i=1;i<=n;++i)f[i][0]=hei[i];
for(register int j=1;j<lg[n];++j)
for(register int i=1;i+(1<<j)-1<=n;++i)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int query(int l,int r){
int len=lg[r-l+1]-1;
return min(f[l][len],f[r-(1<<len)+1][len]);
}
inline int lcp(int i,int j){
return query(min(rk[i],rk[j])+1,max(rk[i],rk[j]));
}
void init(){
memset(tp,0,sizeof tp);
Ssort(),get_height(),ST();
}
}pre,suf;
inline void add(int l,int r,long long *a){
if(r<1)return;
if(l<=n)++a[max(l,1)];
if(r<n)--a[r+1];
}
inline int LCS(int x,int y){
if(!x||!y)return 0;
return pre.lcp(n-x+1,n-y+1);
}
inline int LCP(int x,int y){
return suf.lcp(x,y);
}
int main(){
int t=read();
long long ans;
for(register int i=1;i<maxn;++i)
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
while(t--){
scanf("%s",suf.s+1),n=strlen(suf.s+1),ans=0;
memset(st,0,sizeof st),memset(en,0,sizeof en);
for(register int i=1,j=n;i<=n;--j,++i)pre.s[i]=suf.s[j];
pre.init(),suf.init();
for(register int i=1;i<=(n>>1);++i){
for(register int j=i+i;j<=n;j+=i){
int lcs=min(LCS(j-1,j-i-1),i-1),lcp=min(LCP(j,j-i),i),delta=lcs+lcp-i;
if(lcs+lcp<i)continue;
add(j-i-lcs,j-i-lcs+delta,st),add(j+lcp-1-delta,j+lcp-1,en);
}
}
for(register int i=2;i<=n;++i)
st[i]+=st[i-1],en[i]+=en[i-1];
for(register int i=1;i<n;++i)
ans+=en[i]*st[i+1];
printf("%lld\n",ans);
}
}
后记：
数据千万条，清空第一条。
多测不清空，爆零两行泪。
$SA$要清空$tp$数组。。。蒟蒻调了一小时才发现的$QAQ$
还有蒟蒻想知道$LCS$有没有简便一点的$O(1)$求法。翻转字符串造$SA$感觉太暴力了。。。
