bzoj 4650[Noi2016]优秀的拆分

bzoj 4650[Noi2016]优秀的拆分

​​ Description 如果一个字符串可以被拆分为 AABBAABB 的形式，其中 AA 和 BB 是任意非空字符串，则我们称该字符串的这种拆 分是优秀的。例如，对于字符串 aabaabaa，如果令 A=aabA=aab，B=aB=a，我们就找到了这个字符串拆分成 AABBA ABB 的一种方式。一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 A=aA=a，B=baa B=baa，也可以用 AABBAABB 表示出上述字符串；但是，字符串 abaabaa 就没有优秀的拆分。现在给出一个长度为 nn 的字符串 SS，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串 中连续的一段。以下事项需要注意：出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被 记入答案。在一个拆分中，允许出现 A=BA=B。例如 cccc 存在拆分 A=B=cA=B=c。字符串本身也是它的一个子串。

Input 每个输入文件包含多组数据。输入文件的第一行只有一个整数 TT，表示数据的组数。保证 1≤T≤101≤T≤10。接 下来 TT 行，每行包含一个仅由英文小写字母构成的字符串 SS，意义如题所述。 Output 输出 TT 行，每行包含一个整数，表示字符串 SS 所有子串的所有拆分中，总共有多少个是优秀的拆分。

Sample Input 4 aabbbb cccccc aabaabaabaa bbaabaababaaba Sample Output 3 5 4 7 我们用 S[i,j]S[i,j] 表示字符串 SS 第 ii 个字符到第 jj 个字符的子串（从 11 开始计数）。第一组数据中， 共有 33 个子串存在优秀的拆分：S[1,4]=aabbS[1,4]=aabb，优秀的拆分为 A=aA=a，B=bB=b；S[3,6]=bbbbS[3,6] =bbbb，优秀的拆分为 A=bA=b，B=bB=b；S[1,6]=aabbbbS[1,6]=aabbbb，优秀的拆分为 A=aA=a，B=bbB=bb。而剩 下的子串不存在优秀的拆分，所以第一组数据的答案是 33。第二组数据中，有两类，总共 44 个子串存在优秀的 拆分：对于子串 S[1,4]=S[2,5]=S[3,6]=ccccS[1,4]=S[2,5]=S[3,6]=cccc，它们优秀的拆分相同，均为 A=cA=c， B=cB=c，但由于这些子串位置不同，因此要计算 33 次；对于子串 S[1,6]=ccccccS[1,6]=cccccc，它优秀的拆分 有 22 种：A=cA=c，B=ccB=cc 和 A=ccA=cc，B=cB=c，它们是相同子串的不同拆分，也都要计入答案。所以第二组 数据的答案是 3+2=53+2=5。第三组数据中，S[1,8]S[1,8] 和 S[4,11]S[4,11] 各有 22 种优秀的拆分，其中 S[1 ,8]S[1,8] 是问题描述中的例子，所以答案是 2+2=42+2=4。第四组数据中，S[1,4]S[1,4]，S[6,11]S[6,11]，S[7 ,12]S[7,12]，S[2,11]S[2,11]，S[1,8]S[1,8] 各有 11 种优秀的拆分，S[3,14]S[3,14] 有 22 种优秀的拆分， 所以答案是 5+2=75+2=7。 HINT

Source 暴力分给到95

枚举一个点看左边aa的类型有多少个 右边aa类型 有多少个

考虑枚举长度 然后枚举这个长度间隔选择两个点 然后可以发现我任意区间长度为2*l 的区间一定包含 区间上任意的两个关键点所以我们考虑枚举这个关键点计算答案

然后枚举长度再枚举所有长度的段的复杂度是调和级数n*log(n)

那么我们只需要考虑这两个点分别是i,j 那么算i-1,j-1的最长公共前缀 再算i,j的最长公共后缀

然后我们发现最长公共前缀+最长公共后缀 -len就是我们想要的答案 仔细画图可知 相当于这个是一个长度区间都满足这个aa类型的 但是是区间都满足所以考虑差分 然后最后再累加起来即可

这题uoj恶心数据卡没有给s数组清0

#include#define ll long longusing namespace std;const int N=30030;int T,Log[N],n,ed[N],st[N];struct SA{ int sa[N],rk[N<<1],rk1[N<<1],tmp[N],cnt[N],height[N]; char s[N];int mn[N][20]; inline void build(){ int m=300,k=0; memset(rk,0,sizeof(rk));memset(rk1,0,sizeof(rk1)); for (int i=1;i<=m;++i) cnt[i]=0; for (int i=1;i<=n;++i) cnt[s[i]]=1; for (int i=1;i<=m;++i) cnt[i]+=cnt[i-1]; for (int i=1;i<=n;++i) rk[i]=cnt[s[i]]; for (int p=1;k!=n;p<<=1,m=k){ for (int i=1;i<=m;++i) cnt[i]=0; for (int i=1;i<=n;++i) ++cnt[rk[i+p]]; for (int i=1;i<=m;++i) cnt[i]+=cnt[i-1]; for (int i=n;i;--i) tmp[cnt[rk[i+p]]--]=i; for (int i=1;i<=m;++i) cnt[i]=0; for (int i=1;i<=n;++i) ++cnt[rk[i]]; for (int i=1;i<=m;++i) cnt[i]+=cnt[i-1]; for (int i=n;i;--i) sa[cnt[rk[tmp[i]]]--]=tmp[i]; memcpy(rk1,rk,sizeof(rk)>>1);rk[sa[1]]=k=1; for (int i=2;i<=n;++i){ if(rk1[sa[i]]!=rk1[sa[i-1]]||rk1[sa[i]+p]!=rk1[sa[i-1]+p]) ++k; rk[sa[i]]=k; } }k=0; for (int i=1;i<=n;++i){ if(rk[i]==1) continue; k=k==0?0:k-1; while(i+k<=n&&sa[rk[i]-1]+k<=n&&s[i+k]==s[sa[rk[i]-1]+k]) ++k; height[rk[i]]=k; } /*for (int i=1;i<=n;++i){ for (int j=sa[i];j<=n;++j) printf("%c",s[j]);puts(""); } for (int i=1;i<=n;++i) printf("%d\n",height[i]);*/ for (int i=1;i<=n;++i) mn[i][0]=height[i]; for (int j=1;j<=Log[n];++j){ for (int i=1;i+(1<y) swap(x,y);++x;int t=Log[y-x+1]; return min(mn[x][t],mn[y-(1<>1]+1; while(T--){ scanf("%s",a.s+1);n=strlen(a.s+1); for (int i=1;i<=n;++i) b.s[i]=a.s[n-i+1]; a.build();b.build();ll ans=0; memset(st,0,sizeof(st));memset(ed,0,sizeof(ed)); for (int l=1;l<=n>>1;++l){ for (int i=l,j=i+l;j<=n;i+=l,j+=l){ int pre=min(b.lcp(n-(i-1)+1,n-(j-1)+1),l-1),suc=min(a.lcp(i,j),l); int t=pre+suc-l+1; if (t>0){ ++st[i-pre];--st[i-pre+t]; ++ed[j+suc-t];--ed[j+suc]; } } } for (int i=1;i<=n;++i) st[i]+=st[i-1],ed[i]+=ed[i-1]; for (int i=1;i<=n;++i) ans+=(ll)ed[i]*st[i+1]; printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。