优秀的拆分
题解
看到题目，数据范围有点怪异。
对于95%的数据，
对于100%的数据，。
意思是只有5分是正解。
好吧,95pts的还是很好想的，我们可以维护出a，b两个数组，
代表以i为结尾的AA型字符串，
代表从i开始的BB型字符串。
很明显,答案就是，a数组与b数组都可以用hash暴力求出来，之后
就可以跑出来了。
而如何才能拿到100pts呢？我们可以先枚举A段的长度，很明显每个长度为的AA串都至少会经过2个关键节点，我们只要从关键节点向前求LCP，与往后求LCS，若
，就一定存在长度为len的AA串，我们可以通过前缀和差分将其二分求出，用哈希进行判断。
这样就可以通过的时间求出。
源码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
#define int LL
#define MAXN 30005
const int mo=3e7+7;
#define gc() getchar()
template<typename _T>
inline void read(_T &x){
_T f=1;x=0;char s=gc();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}
while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}
x*=f;
}
int t,a[MAXN],b[MAXN],n;
int powm[MAXN],hash[MAXN];
char ns[MAXN];
int getHash(int l,int r){
return ((hash[l]-hash[r]*powm[r-l])%mo+mo)%mo;
}
signed main(){
powm[0]=1;
for(int i=1;i<=30000;i++)powm[i]=powm[i-1]*27%mo;
read(t);
while(t--){
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
scanf("\n%s",ns);n=(int)strlen(ns);hash[n+1]=0;
for(int i=n;i>0;i--)hash[i]=(hash[i+1]*27+ns[i-1]-'a'+1)%mo;
for(int len=1;len*2<=n;len++)
for(int i=len<<1;i<=n;i+=len){
if(ns[i-1]!=ns[i-len-1])continue;
int l=1,r=len,las=i-len,ans=0;
while(l<=r){
int mid=l+r>>1;
if(getHash(las-mid+1,las+1)==getHash(i-mid+1,i+1))
ans=mid,l=mid+1;
else r=mid-1;
}
int head=i-ans+1;l=1;r=len;ans=0;
while(l<=r){
int mid=l+r>>1;
if(getHash(las,las+mid)==getHash(i,i+mid))
ans=mid,l=mid+1;
else r=mid-1;
}
int tail=i+ans-1;
head=max(head+len-1,i);tail=min(tail,i+len-1);
if(head<=tail){
++a[head-2*len+1];--a[tail-2*len+2];
++b[head];--b[tail+1];
}
}
int res=0;
for(int i=1;i<=n;i++)a[i]+=a[i-1],b[i]+=b[i-1];
for(int i=1;i<n;i++)res+=b[i]*a[i+1];
printf("%lld\n",res);
}
return 0;
}