BZOJ4650: [Noi2016]优秀的拆分-布布扣-bubuko.com

BZOJ4650: [Noi2016]优秀的拆分

Description

如果一个字符串可以被拆分为 AABBAABB 的形式，其中 AA 和 BB 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。

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

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。

比如我们令 A=a，B=baa，也可以用 AABB 表示出上述字符串；但是，字符串 abaabaa 就没有优秀的拆分。

现在给出一个长度为 n 的字符串 S，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。

这里的子串是指字符串中连续的一段。

以下事项需要注意：出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。

在一个拆分中，允许出现 A=B。例如 cccc 存在拆分 A=B=c。字符串本身也是它的一个子串。

Input

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 T，表示数据的组数。

保证 1≤T≤10。

接下来 T 行，每行包含一个仅由英文小写字母构成的字符串 S，意义如题所述。

Output

输出 T 行，每行包含一个整数，表示字符串 S 所有子串的所有拆分中，总共有多少个是优秀的拆分。

Sample Input

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Sample Output

3
5
4
7

HINT

我们用 S[i,j] 表示字符串 S 第 i 个字符到第 j 个字符的子串（从 1 开始计数）。

第一组数据中，共有 33 个子串存在优秀的拆分：

S[1,4]=aabb，优秀的拆分为 A=a，B=b；

S[3,6]=bbbb，优秀的拆分为 A=b，B=b；

S[1,6]=aabbbb，优秀的拆分为 A=a，B=bb。

而剩下的子串不存在优秀的拆分，所以第一组数据的答案是 3。

第二组数据中，有两类，总共 4 个子串存在优秀的拆分：

对于子串 S[1,4]=S[2,5]=S[3,6]=cccc，它们优秀的拆分相同，均为 A=c，B=c，但由于这些子串位置不同，因此要计算 3 次；

对于子串 S[1,6]=cccccc，它优秀的拆分有 2 种：A=c，B=cc 和 A=cc，B=c，它们是相同子串的不同拆分，也都要计入答案。

所以第二组数据的答案是 3+2=5。

第三组数据中，S[1,8] 和 S[4,11] 各有 2 种优秀的拆分，其中 S[1,8] 是问题描述中的例子，所以答案是 2+2=4。

第四组数据中，S[1,4]，S[6,11]，S[7,12]，S[2,11]，S[1,8] 各有 1 种优秀的拆分，S[3,14] 有 2 种优秀的拆分，所以答案是 5+2=7。

题解Here!

感觉有点像后缀数组。。。

没错就是后缀数组。

显然我们不用处理什么$AABB$，只需要去处理所有$AA$的形式，再去统计答案即可。

设$Left[i]$表示以$i$这个字符开头的$AA$型子串的数目。

设$Right[i]$表示以$i$这个字符结尾的$AA$型子串的数目。

则：$Ans=\sum_{i=1}^{n-1}Left[i+1]\times Right[i]$

顺序求一遍，反过来再求一遍，$Left[i],Right[i]$就可以求解了。

问题是怎么求解。

我们可以枚举找的$AA$型子串长度的一半，去判断$LCP$与$LCS$

枚举$i=k\times len,j=i+len,j<=n$

设$x=LCP(suffix(i),suffix(j)),y=LCS(prefix(i−1),prefix(j−1))$

若$x+y>=len$，那么我们就找到了$x+y−len+1$个长度为$2\times len$的$AA$型子串

差分一下，最后做一遍前缀和即可。

注：记得清空数组。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 50010
using namespace std;
int n;
long long Left[MAXN],Right[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
    return date*w;
}
struct Suffix_Array{
    char str[MAXN];
    int top,sa[MAXN],rk[MAXN],tax[MAXN],tp[MAXN],height[MAXN],f[MAXN][20];
    void radixsort(){
        for(int i=0;i<=top;i++)tax[i]=0;
        for(int i=1;i<=n;i++)tax[rk[i]]++;
        for(int i=1;i<=top;i++)tax[i]+=tax[i-1];
        for(int i=n;i>=1;i--)sa[tax[rk[tp[i]]]--]=tp[i];
    }
    void suffixsort(){
        top=128;
        for(int i=1;i<=n;i++){
            rk[i]=str[i];
            tp[i]=i;
        }
        radixsort();
        for(int w=1,p=0;p<n;top=p,w<<=1){
            p=0;
            for(int i=1;i<=w;i++)tp[++p]=n-w+i;
            for(int i=1;i<=n;i++)if(sa[i]>w)tp[++p]=sa[i]-w;
            radixsort();
            swap(tp,rk);
            rk[sa[1]]=p=1;
            for(int i=2;i<=n;i++)
            rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
        }
    }
    void getheight(){
        for(int i=1,j,k=0;i<=n;i++){
            if(k)k--;
            j=sa[rk[i]-1];
            while(str[i+k]==str[j+k])k++;
            height[rk[i]]=k;
        }
    }
    void step(){
        for(int i=1;i<=n;i++)f[i][0]=height[i];
        for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
        f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
    }
    int query(int l,int r){
        l=rk[l];r=rk[r];
        if(l>r)swap(l,r);
        l++;
        int k=(int)log2(r-l+1);
        return min(f[l][k],f[r-(1<<k)+1][k]);
    }
    inline void clean(){
        memset(str,0,sizeof(str));
        memset(sa,0,sizeof(sa));
        memset(rk,0,sizeof(rk));
        memset(height,0,sizeof(height));
        memset(tp,0,sizeof(tp));
        memset(f,0,sizeof(f));
    }
    inline void build(){
        suffixsort();
        getheight();
        step();
    }
}A,B;
void work(){
    long long ans=0;
    for(int k=1;k<=(n>>1);k++)
    for(int i=k,j=i+k;j<=n;i+=k,j+=k){
        int x=min(k,A.query(i,j)),y=min(k-1,B.query(n-(i-1)+1,n-(j-1)+1));
        if(x+y>=k){
            int t=x+y-k+1;
            Left[i-y]++;Left[i-y+t]--;
            Right[j+x-t]++;Right[j+x]--;
        }
    }
    for(int i=1;i<=n;i++){
        Left[i]+=Left[i-1];
        Right[i]+=Right[i-1];
    }
    for(int i=1;i<=n;i++)ans+=Left[i+1]*Right[i];
    printf("%lld\n",ans);
}
void init(){
    memset(Left,0,sizeof(Left));
    memset(Right,0,sizeof(Right));
    A.clean();B.clean();
    scanf("%s",A.str+1);
    n=strlen(A.str+1);
    for(int i=1;i<=n;i++)B.str[i]=A.str[n-i+1];
    A.build();B.build();
}
int main(){
    int t=read();
    while(t--){
        init();
        work();
    }
    return 0;
}

BZOJ4650: [Noi2016]优秀的拆分

原文：https://www.cnblogs.com/Yangrui-Blog/p/9458910.html