[bzoj 4650][NOI 2016]优秀的拆分

传送门

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<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[27];
    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！