传送门
Description
如果一个字符串可以被拆分为\(AABB\) 的形式，其中$ A$和 \(B\)是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串\(aabaabaa\)，如果令\(A=aab\)，\(B=a\)，我们就找到了这个字符串拆分成 \(AABB\)的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令\(A=a\)，\(B=baa\)，也可以用 \(AABB\)表示出上述字符串；但是，字符串 \(abaabaa\) 就没有优秀的拆分。
现在给出一个长度为 \(n\)的字符串\(S\)，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
- 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
- 在一个拆分中，允许出现\(A=B\)。例如 \(cccc\) 存在拆分\(A=B=c\) 。
- 字符串本身也是它的一个子串。
Solution
\(st[i]\)表示以\(i\)开始的有多少个形式如\(aa\)的子串
\(en[i]\)表示以\(j\)结束的有多少个形式如\(aa\)的字串
那么答案就是\(\sum_{i=1}^{n-1} en[i]*st[i+1]\)
怎么求这个东西呢？只考虑\(st\)，因为把原字符串倒个序就能求\(en\)了
枚举\(aa\)中\(a\)的长度，然后每次我们只考虑\([ka+1,(k+1)a]\)这个区间上有多少个可以作为起始点的，它一定包含\((k+1)a\)这个位置，而后面与它相同的字串一定包括\((k+2)a\)这个位置，所以直接查询\(LCP((k+1)a,(k+2)a)\),以及\(LCS((k+1)a,(k+2)a)\)，就可以啦。
根据调和级数和\(SA\)，总复杂度是\(O(n\log n)\)
Code
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
#define MN 30005
#define M(a) memset(a,0,sizeof a);
char s[MN];
int lg[MN],en[MN],st[MN],n;void init(){n=strlen(s+1);M(st);M(en);}class SA
{private:int height[MN][19],p,q,sa[2][MN],rk[2][MN],num[MN];public:SA(){M(height);M(sa);M(rk);M(num);}inline void init(){M(height);M(sa);M(rk);M(num);}inline void build_sa(){register int i,j,k,mx;for(i=1;i<=n;++i) num[s[i]-'a'+1]++;for(i=1;i<=26;++i) num[i]+=num[i-1];for(i=1;i<=n;++i) sa[1][num[s[i]-'a'+1]--]=i;for(i=1;i<=n;++i) rk[1][sa[1][i]]=rk[1][sa[1][i-1]]+(s[sa[1][i-1]]!=s[sa[1][i]]);mx=rk[1][sa[1][n]];for(p=1,q=0,k=1;k<=n;k<<=1,p^=1,q^=1){if(mx==n) break;for(i=1;i<=n;++i) num[rk[p][sa[p][i]]]=i;for(i=n;i;--i) if(sa[p][i]>k) sa[q][num[rk[p][sa[p][i]-k]]--]=sa[p][i]-k;for(i=n-k+1;i<=n;++i) sa[q][num[rk[p][i]]--]=i;for(i=1;i<=n;++i)rk[q][sa[q][i]]=rk[q][sa[q][i-1]]+(rk[p][sa[q][i]]!=rk[p][sa[q][i-1]]||rk[p][sa[q][i]+k]!=rk[p][sa[q][i-1]+k]);mx=rk[q][sa[q][n]];}for(i=k=1;i<=n;++i){if(rk[p][i]==1) continue;if(k) k--;for(j=sa[p][rk[p][i]-1];j+k<=n&&i+k<=n&&s[i+k]==s[j+k];++k);height[rk[p][i]][0]=k;}for(i=1;i<=18;++i)for(j=n;j>=1&&j>(1<<i);--j)height[j][i]=min(height[j][i-1],height[j-(1<<i-1)][i-1]);}inline int LCP(int x,int y){x=rk[p][x];y=rk[p][y];if(x>y) std::swap(x,y);return min(height[y][lg[y-x]],height[x+(1<<lg[y-x])][lg[y-x]]);}
}A,revA;int main()
{register int T,i,j;for(i=2;i<MN;++i) lg[i]=lg[i>>1]+1;T=read();printf("%d\n",T);while(T--){memset(s,0,sizeof s);scanf("%s",s+1);init();A.init();A.build_sa();for(i=1;i+i<=n;++i) std::swap(s[i],s[n-i+1]);revA.init();revA.build_sa();register int len,x,y;for(len=1;len<=n;++len)for(i=len,j=len<<1;j<=n;i+=len,j+=len){x=min(A.LCP(i,j),len);y=min(revA.LCP(n-i+1,n-j+1),len);if(x+y-1<len) continue;st[i-y+1]++;st[i+x-len+1]--;en[j+len-y]++;en[j+x]--;}for(i=1;i<=n;++i) st[i]+=st[i-1],en[i]+=en[i-1];register ll ans=0;for(i=1;i<n;++i) ans+=1ll*en[i]*st[i+1];printf("%lld\n",ans);}return 0;
}Blog来自PaperCloud，未经允许，请勿转载，TKS！
