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

水深无声 2022-01-09 07:41 233阅读 0赞

## [ 传送门 ][Link 1] ##

## **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[MN]; 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！

转载于:https://www.cnblogs.com/PaperCloud/p/10258179.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=4650