BZOJ 4650 [Noi2016]优秀的拆分：后缀数组

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4650

题意：

　　给你一个字符串s，问你s及其子串中，将它们拆分成"AABB"的方式共有多少种。

题解：

　　先只考虑"AA"的形式。

　　设pre[i]表示以s[i]结尾的"AA"串共有多少个，nex[i]表示以s[i]开头的"AA"串共有多少个。

　　那么拆分成"AABB"的总方案数 = ∑ pre[i]*nex[i+1]。

　　然后考虑如何求pre和nex数组。

　　对于"AA"形式的串，有一个性质：

　　　　假设一个"AA"串的长度为len。

　　　　如果在s串上每隔len的距离设置一个关键点，那么这个"AA"串一定经过相邻的两个关键点。

　　所以先枚举"AA"串的长度len，然后枚举是哪两个相邻的关键点。

　　设当前的两个相邻关键点分别为：x = i*len, y = (i+1)*len

　　设前缀s[1 to x]和前缀s[1 to y]的LCS为a，后缀s[x to n]和后缀s[y to n]的LCP为b

　　令tt = a+b-1

　　如果有tt >= len，则就找到了a+b-len个长度为len的"AA"串。

　　又因为这些"AA"串是必须经过x,y这两个关键点的（否则会重复统计）

　　所以上面的a = min(a,len), b = min(b,len)。

　　找到的这些"AA"串会对pre数组和nex数组产生贡献。

　　所有这些"AA"串的开头为区间[x-a+1, x+b-len]，结尾为区间[y-a+len, y+b-1]。

　　所以要给nex[x-a+1 to x+b-len]加1，给pre[y-a+len to y+b-1]加1

　　差分一下，最后求一遍前缀个就好。

　　这样pre和nex就求好了，然后统计"AABB"的总数即可。

　　O(nlogn)求后缀数组

　　O(nlogn)求pre和nex（调和级数复杂度）

　　O(n)统计"AABB"

　　总复杂度O(nlogn)

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 30005

 #define MAX_K 20

 using namespace std;

 struct SA

 {

     int n;

     int a[MAX_N];

     int sa[MAX_N];

     int rk[MAX_N];

     int t1[MAX_N];

     int t2[MAX_N];

     int cnt[MAX_N];

     int tsa[MAX_N];

     int height[MAX_N];

     char s[MAX_N];

     int lg[MAX_N];

     int dat[MAX_N][MAX_K];

     void rsort()

     {

         memset(cnt,,sizeof(cnt));

         for(int i=;i<=n;i++) cnt[t2[i]]++;

         for(int i=;i<=n;i++) cnt[i]+=cnt[i-];

         for(int i=n;i>=;i--) tsa[cnt[t2[i]]--]=i;

         memset(cnt,,sizeof(cnt));

         for(int i=;i<=n;i++) cnt[t1[i]]++;

         for(int i=;i<=n;i++) cnt[i]+=cnt[i-];

         for(int i=n;i>=;i--) sa[cnt[t1[tsa[i]]]--]=tsa[i];

     }

     void suffix()

     {

         memset(cnt,,sizeof(cnt));

         for(int i=;i<=n;i++) a[i]=s[i],cnt[a[i]]++;

         for(int i='a';i<='z';i++) cnt[i]+=cnt[i-];

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

         int len=;

         while(len<n)

         {

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

             {

                 t1[i]=rk[i];

                 t2[i]=i+len<=n ? rk[i+len] : ;

             }

             rsort();

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

             {

                 rk[sa[i]]=rk[sa[i-]]+(t1[sa[i]]!=t1[sa[i-]] || t2[sa[i]]!=t2[sa[i-]]);

             }

             len<<=;

         }

         int k=;

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

         {

             k=k?k-:k;

             int j=sa[rk[i]-];

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

             height[rk[i]]=k;

         }

     }

     void init_st()

     {

         lg[]=-;

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

         {

             lg[i]=lg[i>>]+;

             dat[i][]=height[i];

         }

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

         {

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

             {

                 dat[i][k]=min(dat[i][k-],dat[i+(<<(k-))][k-]);

             }

         }

     }

     int lcp(int l,int r)

     {

         l=rk[l]; r=rk[r];

         if(l>r) swap(l,r); l++;

         int k=lg[r-l+];

         return min(dat[l][k],dat[r-(<<k)+][k]);

     }

     void init(char *_s,int _n)

     {

         memset(a,,sizeof(a));

         memset(sa,,sizeof(sa));

         memset(rk,,sizeof(rk));

         memset(tsa,,sizeof(tsa));

         memset(height,,sizeof(height));

         n=_n;

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

         suffix();

         init_st();

     }

 };

 int n,t;

 char str[MAX_N];

 char rev[MAX_N];

 long long ans;

 long long pre[MAX_N];

 long long nex[MAX_N];

 SA sa1,sa2;

 inline void add(long long *a,int l,int r)

 {

     a[l]++; a[r+]--;

 }

 void cal_aa()

 {

     memset(pre,,sizeof(pre));

     memset(nex,,sizeof(nex));

     for(int len=;len<=n/;len++)

     {

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

         {

             int x=i*len,y=(i+)*len;

             int a=sa2.lcp(n-x+,n-y+),b=sa1.lcp(x,y);

             a=min(a,len); b=min(b,len);

             int tt=a+b-;

             if(tt>=len)

             {

                 add(nex,x-a+,x+b-len);

                 add(pre,y-a+len,y+b-);

             }

         }

     }

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

     {

         pre[i]+=pre[i-];

         nex[i]+=nex[i-];

     }

 }

 void cal_aabb()

 {

     ans=;

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

     {

         ans+=pre[i]*nex[i+];

     }

 }

 int main()

 {

     scanf("%d",&t);

     while(t--)

     {

         scanf("%s",str+);

         n=strlen(str+);

         for(int i=,j=n;i<=n;i++,j--) rev[j]=str[i];

         sa1.init(str,n); sa2.init(rev,n);

         cal_aa();

         cal_aabb();

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

     }

 }

巴特西

BZOJ 4650 [Noi2016]优秀的拆分：后缀数组

最新文章

热门文章