由于字符串是AABB的形式，枚举AA和BB中间的位置，分别考虑AA和BB的数量，乘起来sigma一下即为答案
以下考虑AA的情况（BB同理），枚举A的长度，然后按照这个长度分为若干块，那么每一个A一定可以表示成某一段的结尾+下一段的开头，同时两个A又要连续，也就是相邻两块的lcp和lcs，用差分来维护即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 30005 4 #define mod 998244353 5 #define mid (l+r+1>>1) 6 int t,n,sum[N],mi[N],f1[N],f2[N]; 7 long long ans; 8 char s[N]; 9 int hash(int x,int y){ 10 if (y<x)return 0; 11 if (!x)return sum[y]; 12 return (sum[y]-1LL*sum[x-1]*mi[y-x+1]%mod+mod)%mod; 13 } 14 bool pd(int x1,int y1,int x2,int y2){ 15 return hash(x1,y1)==hash(x2,y2); 16 } 17 void calc(int x,int y){ 18 int l=0,r=min(y-x,n-y),p=0; 19 while (l<r) 20 if (pd(x,x+mid-1,y,y+mid-1))l=mid; 21 else r=mid-1; 22 swap(l,p); 23 r=min(x+1,y-x-1); 24 while (l<r) 25 if (pd(x-mid,x-1,y-mid,y-1))l=mid; 26 else r=mid-1; 27 l=p; 28 if (l+r<y-x)return; 29 f1[x-r]++; 30 f1[2*x-y+l+1]--; 31 f2[2*y-x-r-1]++; 32 f2[y+l]--; 33 } 34 int main(){ 35 scanf("%d",&t); 36 mi[0]=1; 37 for(int i=1;i<N-4;i++)mi[i]=mi[i-1]*31LL%mod; 38 while (t--){ 39 scanf("%s",s); 40 memset(f1,0,sizeof(f1)); 41 memset(f2,0,sizeof(f2)); 42 n=strlen(s); 43 sum[0]=s[0]-'a'+1; 44 for(int i=1;i<n;i++)sum[i]=(sum[i-1]*31LL+s[i]-'a'+1)%mod; 45 for(int i=1;i<=n;i++) 46 for(int j=i-1;j+i<n;j+=i)calc(j,j+i); 47 ans=0; 48 for(int i=1;i<n;i++){ 49 f1[i]+=f1[i-1]; 50 f2[i]+=f2[i-1]; 51 ans+=1LL*f1[i]*f2[i-1]; 52 } 53 printf("%lld ",ans); 54 } 55 }