Description

如果一个字符串可以被拆分为\(AABB\) 的形式，其中$ A$和 \(B\)是任意非空字符串，则我们称该字符串的这种拆分是优秀的。

例如，对于字符串\(aabaabaa\)，如果令\(A=aab\)，\(B=a\)，我们就找到了这个字符串拆分成 \(AABB\)的一种方式。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令\(A=a\)，\(B=baa\)，也可以用 \(AABB\)表示出上述字符串；但是，字符串 \(abaabaa\) 就没有优秀的拆分。

现在给出一个长度为 \(n\)的字符串\(S\)，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

1. 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
2. 在一个拆分中，允许出现\(A=B\)。例如 \(cccc\) 存在拆分\(A=B=c\) 。
3. 字符串本身也是它的一个子串。

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
    
     #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<
     
      y) std::swap(x,y);            return min(height[y][lg[y-x]],height[x+(1<
      
       >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
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！