BZOJ4650：[NOI2016]优秀的拆分—

https://www.lydsy.com/JudgeOnline/problem.php?id=4650

https://www.luogu.org/problemnew/show/P1117

如果一个字符串可以被拆分为 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.字符串本身也是它的一个子串。

这类题的方法还是见少了啊，听说神犇都是一眼秒的，果然还是有很大的差距啊，唉……

对于AABB，我们完全可以只考虑AA，这样令f[i]表示以i结尾的AA数量，g[i]表示以i开头的AA数量，那么显然就是sigma(f[i]g[i+1])。

对于AA怎么求，大体的思路和URAL1297：Palindrome求回文串是一样的，就是通过比较后缀的公共前缀来得到AA的长度，进而求出这段区间内f[i]g[i]的值。

但是这样显然是O(n^2)的。

我们用（黑）分（科）块（技）的思想，枚举l，将字符串分成l大小的块，则长度为l的AA一定最少跨过两个块，于是对于块边界点，求一次公共前缀和后缀，拼在一起就是我们所要的答案，复杂度调和级数O(nlogn)。

注意，为了让复杂度正确，我们对区间的f和g差分。

#include<cstdio>

#include<cmath>

#include<iostream>

#include<vector>

#include<cstring>

#include<algorithm>

#include<cctype>

using namespace std;

typedef long long ll;

const int N=2e6+;

char s[N];

int n,m,rk[N],height[N],sa[N],w[N],cas,dp[N][],lg[N];

int f[N],g[N];

inline int qpow(int a){return <<a;}

inline bool pan(int *x,int i,int j,int k){

    int ti=i+k<n?x[i+k]:-;

    int tj=j+k<n?x[j+k]:-;

    return ti==tj&&x[i]==x[j];

}

void SA_init(){

    int *x=rk,*y=height,r=;

    for(int i=;i<r;i++)w[i]=;

    for(int i=;i<n;i++)w[s[i]]++;

    for(int i=;i<r;i++)w[i]+=w[i-];

    for(int i=n-;i>=;i--)sa[--w[s[i]]]=i;

    r=;x[sa[]]=;

    for(int i=;i<n;i++)

    x[sa[i]]=s[sa[i]]==s[sa[i-]]?r-:r++;

    for(int k=;r<n;k<<=){

    int yn=;

    for(int i=n-k;i<n;i++)y[yn++]=i;

    for(int i=;i<n;i++)

        if(sa[i]>=k)y[yn++]=sa[i]-k;

    for(int i=;i<r;i++)w[i]=;

    for(int i=;i<n;i++)w[x[y[i]]]++;

    for(int i=;i<r;i++)w[i]+=w[i-];

    for(int i=n-;i>=;i--)sa[--w[x[y[i]]]]=y[i];

    swap(x,y);r=;x[sa[]]=;

    for(int i=;i<n;i++)

        x[sa[i]]=pan(y,sa[i],sa[i-],k)?r-:r++;

    }

}

inline void height_init(){

    int i,j,k=;

    for(int i=;i<=n;i++)rk[sa[i]]=i;

    for(int i=;i<n;i++){

    if(k)k--;

    j=sa[rk[i]-];

    while(s[i+k]==s[j+k])k++;

    height[rk[i]]=k;

    }

}

void st_init(){

    for(int i=;i<=n;i++){

    dp[i-][]=height[i];

    lg[i]=lg[i-];

    if((<<lg[i]+)==i)lg[i]++;

    }

    for(int j=;j<=lg[n];j++){

    for(int i=;i<n;i++){

        if(i+qpow(j)->=n)break;

        dp[i][j]=min(dp[i][j-],dp[i+qpow(j-)][j-]);

    }

    }

}

int lcp(int a,int b){

    int l=rk[a],r=rk[b];

    if(r<l)swap(l,r);

    l--;r--;

    if(r<)return ;

    l++;

    int len=r-l+;

    int k=lg[len];

    int h=qpow(k);

    return min(dp[l][k],dp[r-h+][k]);

}

int main(){

    scanf("%d",&cas);

    while(cas--){

    memset(f,,sizeof(f));

    memset(g,,sizeof(g));

    cin>>s;

    m=strlen(s),n=*m+;

    s[m]='$';

    for(int i=m+;i<n;i++){

        s[i]=s[n-i-];

    }

    s[n++]=;

    SA_init();

    n--;

    height_init();

    st_init();

    for(int l=;l<=m/;l++){

        for(int i=,j=l;j<m;i+=l,j+=l){

        int p=min(l,lcp(i,j));

        int s=min(l,lcp(n-i-,n-j-));

        if(p+s->=l){

                    f[j-s+l]++;f[j+p]--;

            g[i-s+]++;g[i+p-l+]--;

        }

        }

    }

    ll ans=;

    for(int i=;i<m;i++){

        f[i]+=f[i-];

        g[i]+=g[i-];

    }

    for(int i=;i<m-;i++){

        ans+=(ll)f[i]*g[i+];

    }

    printf("%lld\n",ans);

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ4650：[NOI2016]优秀的拆分——题解

最新文章

热门文章