[bzoj4650]-[NOI2016]优秀的拆分

题目（BZOJ）
题目（洛谷）
题目（LibreOJ）
 
这题首先就不管那个AABB...直接找AA就可以了。
设f[i]为以i开头的AA子串个数，g[i]为以i结尾的AA子串个数。
然后瞎统计一下就可以了。
统计时要求LCS和LCP，这时开两个后缀数组，分别存LCS和LCP就可以了~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;int ck=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=-1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	e*=ck;
}
const int N=30050;
char s[N];ll ans;int n;
ll f[N],g[N];
inline int idx(char c){return c-'a'+1;}
struct Suffix_Array{
	int p,q,k,a[N],v[N],h[N],sa[2][N],rk[2][N],st[N][16];
	inline void mulsa(int *sa,int *rk,int *SA,int *RK){
		for(int i=1;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+1;i<=n;++i)SA[v[rk[i]]--]=i;
		for(int i=1;i<=n;++i)RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
	}
	inline void initsa(){
		for(int i=1;i<=n;++i)v[a[i]]++;
		for(int i=1;i<=30;++i)v[i]+=v[i-1];
		for(int i=1;i<=n;++i)sa[p][v[a[i]]--]=i;
		for(int i=1;i<=n;++i)rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);
		for(k=1;k<n;k<<=1,swap(p,q))mulsa(sa[p],rk[p],sa[q],rk[q]);
		for(int i=1,k=0;i<=n;++i){
			int j=sa[p][rk[p][i]-1];
			while(a[i+k]==a[j+k])++k;
			h[rk[p][i]]=k;if(k>0)--k;
		}
	}
	inline void initlcp(){
		for(int i=1;i<=n;++i)st[i][0]=h[i];
		for(int j=1;j<=15;++j)
			for(int i=1;i+(1<<j)-1<=n;++i)
				st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
	inline int lcp(int x,int y){
		if(x>y)swap(x,y);++x;
		int k=0;
		while(x+(1<<(k+1))<=y)++k;
		return min(st[x][k],st[y-(1<<k)+1][k]);
	}
	inline void data_clear(){
		memset(sa,0,sizeof sa),k=0,p=0,q=1;
		memset(rk,0,sizeof rk);
		memset(v,0,sizeof v);
		memset(h,0,sizeof h);
		memset(st,0,sizeof st);
	}
};
Suffix_Array A,B;
int main(){
	int Test;read(Test);
	while(Test--){
		memset(f,0,sizeof f),memset(g,0,sizeof g);ans=0;
		A.data_clear();B.data_clear();
		scanf(
		for(int i=1;i<=n;++i)A.a[i]=idx(s[i]),B.a[i]=idx(s[n-i+1]);
		A.initsa();B.initsa();A.initlcp();B.initlcp();
		for(int i=1;i*2<=n;++i){
			for(int j=i+1;j<=n;j+=i){
				if(s[j]!=s[j-i])continue;
				int suf=min(A.lcp(A.rk[A.p][j],A.rk[A.p][j-i]),i);
				int pre=min(B.lcp(B.rk[B.p][n-j+2],B.rk[B.p][n-j+i+2]),i-1);
				int tmp=pre+suf-i+1;
				if(tmp>0){
					g[j-i-pre]++,g[j-i-pre+tmp]--;
					f[j+i-pre-1]++,f[j+i-pre-1+tmp]--;
				}
			}
		}
		for(int i=1;i<=n;++i)f[i]+=f[i-1],g[i]+=g[i-1];
		for(int i=1;i<=n;++i)ans+=f[i]*g[i+1];
		printf(
	}
	return 0;
}