如果一个字符串可以被拆分为 \(AABB\) 的形式, 其中 $A 和 B 是任意非空字符串, 则我们称该字符串的这种拆分是优秀的.
例如, 对于字符串 \(aabaabaa\), 如果令 \(A=aab\),\(B=a\), 我们就找到了这个字符串拆分成 \(AABB\) 的一种方式.
一个字符串可能没有优秀的拆分, 也可能存在不止一种优秀的拆分. 比如我们令 \(A=a\),\(B=baa\), 也可以用 AABB 表示出上述字符串; 但是, 字符串 \(abaabaa\) 就没有优秀的拆分.
现在给出一个长度为 \(n\) 的字符串 \(S\), 我们需要求出, 在它所有子串的所有拆分方式中, 优秀拆分的总个数. 这里的子串是指字符串中连续的一段.
以下事项需要注意:
出现在不同位置的相同子串, 我们认为是不同的子串, 它们的优秀拆分均会被记入答案.
在一个拆分中, 允许出现 \(A=B\). 例如 \(cccc\) 存在拆分 \(A=B=c\).
字符串本身也是它的一个子串.
对于 \(AABB\), 我们完全可以只考虑 \(AA\), 这样令 \(f[i]\) 表示以 i 结尾的 \(AA\) 数量,\(g[i]\) 表示以 \(i\) 开头的 \(AA\) 数量, 那么显然就是 \(sigma(f[i]g[i+1])\).
对于 \(AA\) 怎么求, 大体的思路和 URAL1297:Palindrome http://acm.timus.ru/problem.aspx?space=1&num=1297 求回文串是一样的, 就是通过比较后缀的公共前缀来得到 AA 的长度, 进而求出这段区间内 \(f[i]g[i]\) 的值.
但是这样显然是 \(O(n^{2})\) 的.
我们用分块的思想, 枚举 \(l\), 将字符串分成 \(l\) 大小的块, 则长度为 \(l\) 的 \(AA\) 一定最少跨过两个块, 于是对于块边界点, 求一次公共前缀和后缀, 拼在一起就是我们所要的答案, 复杂度调和级数 \(O(n*log_{2}^{n})\).
注意, 为了让复杂度正确, 我们对区间的 \(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+10;
- char s[N];
- int n,m,rk[N],height[N],sa[N],w[N],cas,dp[N][21],lg[N];
- int f[N],g[N];
- inline int qpow(int a)
- {
- return 1<<a;
- }
- inline bool pan(int *x,int i,int j,int k)
- {
- int ti=i+k<n?x[i+k]:-1;
- int tj=j+k<n?x[j+k]:-1;
- return ti==tj&&x[i]==x[j];
- }
- void SA_init()
- {
- int *x=rk,*y=height,r=256;
- for(int i=0; i<r; i++)w[i]=0;
- for(int i=0; i<n; i++)w[s[i]]++;
- for(int i=1; i<r; i++)w[i]+=w[i-1];
- for(int i=n-1; i>=0; i--)sa[--w[s[i]]]=i;
- r=1;
- x[sa[0]]=0;
- for(int i=1; i<n; i++)
- x[sa[i]]=s[sa[i]]==s[sa[i-1]]?r-1:r++;
- for(int k=1; r<n; k<<=1)
- {
- int yn=0;
- for(int i=n-k; i<n; i++)y[yn++]=i;
- for(int i=0; i<n; i++)
- if(sa[i]>=k)y[yn++]=sa[i]-k;
- for(int i=0; i<r; i++)w[i]=0;
- for(int i=0; i<n; i++)w[x[y[i]]]++;
- for(int i=1; i<r; i++)w[i]+=w[i-1];
- for(int i=n-1; i>=0; i--)sa[--w[x[y[i]]]]=y[i];
- swap(x,y);
- r=1;
- x[sa[0]]=0;
- for(int i=1; i<n; i++)
- x[sa[i]]=pan(y,sa[i],sa[i-1],k)?r-1:r++;
- }
- }
- inline void height_init()
- {
- int i,j,k=0;
- for(int i=1; i<=n; i++)rk[sa[i]]=i;
- for(int i=0; i<n; i++)
- {
- if(k)k--;
- j=sa[rk[i]-1];
- while(s[i+k]==s[j+k])k++;
- height[rk[i]]=k;
- }
- }
- void st_init()
- {
- for(int i=1; i<=n; i++)
- {
- dp[i-1][0]=height[i];
- lg[i]=lg[i-1];
- if((1<<lg[i]+1)==i)lg[i]++;
- }
- for(int j=1; j<=lg[n]; j++)
- {
- for(int i=0; i<n; i++)
- {
- if(i+qpow(j)-1>=n)break;
- dp[i][j]=min(dp[i][j-1],dp[i+qpow(j-1)][j-1]);
- }
- }
- }
- int lcp(int a,int b)
- {
- int l=rk[a],r=rk[b];
- if(r<l)swap(l,r);
- l--;
- r--;
- if(r<0)return 0;
- l++;
- int len=r-l+1;
- int k=lg[len];
- int h=qpow(k);
- return min(dp[l][k],dp[r-h+1][k]);
- }
- int main()
- {
- scanf("%d",&cas);
- while(cas--)
- {
- memset(f,0,sizeof(f));
- memset(g,0,sizeof(g));
- cin>>s;
- m=strlen(s),n=2*m+1;
- s[m]='$';
- for(int i=m+1; i<n; i++)
- {
- s[i]=s[n-i-1];
- }
- s[n++]=0;
- SA_init();
- n--;
- height_init();
- st_init();
- for(int l=1; l<=m/2; l++)
- {
- for(int i=0,j=l; j<m; i+=l,j+=l)
- {
- int p=min(l,lcp(i,j));
- int s=min(l,lcp(n-i-1,n-j-1));
- if(p+s-1>=l)
- {
- f[j-s+l]++;
- f[j+p]--;
- g[i-s+1]++;
- g[i+p-l+1]--;
- }
- }
- }
- ll ans=0;
- for(int i=1; i<m; i++)
- {
- f[i]+=f[i-1];
- g[i]+=g[i-1];
- }
- for(int i=0; i<m-1; i++)
- {
- ans+=(ll)f[i]*g[i+1];
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2893741.html