Description
如果一个字符串可以被拆分为 AABBAABB 的形式，其中 AA 和 BB 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。例如，对于字符串 aaba，如果令 A=aab，B=a，我们就找到了这个字符串拆分成 AABB 的一种方式。一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 A=a，B=baa，也可以用 AABBAABB 表示出上述字符串；但是，字符串 abaabaa 就没有优秀的拆分。现在给出一个长度为 n 的字符串 S，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。以下事项需要注意：出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。在一个拆分中，允许出现 A=BA=B。例如 cc 存在拆分 A=B=c。字符串本身也是它的一个子串。
Input
每个输入文件包含多组数据。输入文件的第一行只有一个整数 T，表示数据的组数。保证 1≤T≤10。接下来 T 行，每行包含一个仅由英文小写字母构成的字符串 S，意义如题所述。
Output
输出 T 行，每行包含一个整数，表示字符串 S 所有子串的所有拆分中，总共有多少个是优秀的拆分。
Sample Input
4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba
Sample Output
3
5
4
7
Solution
对于(95pts)，直接(O(n^2))暴力就好了 话说noi的题部分分这么足的吗...
想拿到最后五分就很恶心了....
我们枚举(AA)这样的串，设(s[i])表示以(i)开头有多少个这样的串，(t[i])表示结束，那么答案就是：
然后考虑怎么快速的求出这玩意。
考虑枚举长度(L)，然后枚举一个(i=k*L)，令(j=i+L)。
设(x=min(L-1,lcs(s[1..i-1],s[1..j-1])),y=min(L,lcp(s[i..n],s[j..n])))，这个可以通过构建后缀数组(rmq) (O(1))求出。
那么如果(x+ygeqslant L)，则代表我们找到了起始点在([i-x,i-x+(x+y-L+1)-1])，这里是因为我们一共找到了(x+y-L+1)个合法串，所以拿一个差分累和就好了。
时间复杂度：(O(nlog n+sum_{i=1}^{n}n/i)=O(nlog n))。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
#define ll long long
void print(ll x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(ll x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 4e5+10;
char s[maxn];
int n,cnt,sp1[maxn],sp2[maxn],sum[maxn],sa[maxn],rk[maxn],h[maxn],lg[maxn],r[maxn][16];
int w1[maxn],rev[maxn],w2[maxn];
void clear() {
memset(s,0,(cnt+10)*4);
memset(w1,0,(cnt+10)*4);
memset(w2,0,(cnt+10)*4);
memset(sp1,0,(cnt+10)*4); // Attention !!
memset(sp2,0,(cnt+10)*4);
}
void get_sa() {
int *x=sp1,*y=sp2,m=200;
for(int i=1;i<=m;i++) sum[i]=0;
for(int i=1;i<=cnt;i++) sum[x[i]=s[i]]++;
for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
for(int i=1;i<=cnt;i++) sa[sum[x[i]]--]=i;
for(int k=1,p=0,t=0;t!=cnt;k<<=1,p=0) {
for(int i=cnt-k+1;i<=cnt;i++) y[++p]=i;
for(int i=1;i<=cnt;i++) if(sa[i]>k) y[++p]=sa[i]-k;
for(int i=1;i<=m;i++) sum[i]=0;
for(int i=1;i<=cnt;i++) sum[x[y[i]]]++;
for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
for(int i=cnt;i;i--) sa[sum[x[y[i]]]--]=y[i];
swap(x,y);x[sa[t=1]]=1;
for(int i=2;i<=cnt;i++)
if(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k]) x[sa[i]]=++t;
else x[sa[i]]=t;
m=t;
}
}
void get_height() {
for(int i=1;i<=cnt;i++) rk[sa[i]]=i;
for(int i=1,p=0;i<=cnt;i++) {
if(p) p--;
while(s[i+p]==s[sa[rk[i]-1]+p]) p++;
h[rk[i]]=p;
}
}
void get_rmq() {
for(int i=2;i<=cnt;i++) lg[i]=lg[i>>1]+1;
for(int i=2;i<=cnt;i++) r[i][0]=h[i];
for(int i=1;i<=15;i++)
for(int j=2;j<=cnt-(1<<(i-1));j++)
r[j][i]=min(r[j][i-1],r[j+(1<<(i-1))][i-1]);
}
int rmq(int x,int y) {
if(x>y) return 0;
int t=lg[y-x];
return min(r[x][t],r[y-(1<<t)+1][t]);
}
int lcp(int x,int y) {
if(rk[x]>rk[y]) swap(x,y);
return rmq(rk[x]+1,rk[y]);
}
void add1(int x,int y) {w1[x]++,w1[y+1]--;}
void add2(int x,int y) {w2[x]++,w2[y+1]--;}
void solve() {
scanf("%s",s+1);n=cnt=strlen(s+1);s[++cnt]='#';
for(int i=1;i<=n;i++) s[++cnt]=s[n-i+1],rev[n-i+1]=cnt;
get_sa(),get_height(),get_rmq();
for(int L=1;L<=n;L++) {
for(int i=L;i<=n;i+=L) {
int j=i+L;if(j>n) break;
int x=min(L-1,lcp(rev[i-1],rev[j-1])),y=min(L,lcp(i,j));
if(x+y<L) continue;
add1(i-x,i-x+(x+y-L+1)-1);
add2(j+y-(x+y-L+1),j+y-1);
}
}
for(int i=1;i<=n;i++) w1[i]+=w1[i-1],w2[i]+=w2[i-1];
ll ans=0;
for(int i=1;i<=n;i++) ans+=1ll*w1[i]*w2[i-1];
write(ans);
}
int main() {
int T;read(T);while(T--) solve(),clear();
return 0;
}