题目描述
如果一个字符串可以被拆分为AABBAABB的形式,其中 A和 B是任意非空字符串,则我们称该字符串的这种拆分是优秀的。
例如,对于字符串aabaabaaaabaabaa,如果令 A=aabA=aab,B=aB=a,我们就找到了这个字符串拆分成 AABBAABB的一种方式。
一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=aA=a,B=baaB=baa,也可以用 AABBAABB表示出上述字符串;但是,字符串 abaabaaabaabaa 就没有优秀的拆分。
现在给出一个长度为 nn的字符串SS,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意:
-
出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
-
在一个拆分中,允许出现A=BA=B。例如 cccccccc 存在拆分A=B=cA=B=c。
-
字符串本身也是它的一个子串。
输入输出格式
输入格式:
每个输入文件包含多组数据。
输入的第一行只有一个整数TT,表示数据的组数。保证 1≤T≤101≤T≤10。
接下来 TT行,每行包含一个仅由英文小写字母构成的字符串SS,意义如题所述。
输出格式:
输出 TT行,每行包含一个整数,表示字符串SS 所有子串的所有拆分中,总共有多少个是优秀的拆分。
输入输出样例
4aabbbbccccccaabaabaabaabbaabaababaaba
3547
说明
我们用S_{i,j}Si,j表示字符串 SS第 ii个字符到第jj个字符的子串(从11开始计数)。
第一组数据中,共有 33个子串存在优秀的拆分:
S_{1,4}=aabbS1,4=aabb,优秀的拆分为A=aA=a,B=bB=b;
S_{3,6}=bbbbS3,6=bbbb,优秀的拆分为 A=bA=b,B=bB=b;
S_{1,6}=aabbbbS1,6=aabbbb,优秀的拆分为 A=aA=a,B=bbB=bb。
而剩下的子串不存在优秀的拆分,所以第一组数据的答案是 33。
第二组数据中,有两类,总共44个子串存在优秀的拆分:
对于子串 S_{1,4}=S_{2,5}=S_{3,6}=ccccS1,4=S2,5=S3,6=cccc,它们优秀的拆分相同,均为A=cA=c,B=cB=c,但由于这些子串位置不同,因此要计算33 次;
对于子串 S_{1,6}=ccccccS1,6=cccccc,它优秀的拆分有 22种:A=cA=c,B=ccB=cc和 A=ccA=cc,B=cB=c,它们是相同子串的不同拆分,也都要计入答案。
所以第二组数据的答案是3+2=53+2=5。
第三组数据中,S_{1,8}S1,8和 S_{4,11}S4,11 各有 22 种优秀的拆分,其中S_{1,8}S1,8 是问题描述中的例子,所以答案是2+2=42+2=4。
第四组数据中,S_{1,4},S_{6,11},S_{7,12},S_{2,11},S_{1,8}S1,4,S6,11,S7,12,S2,11,S1,8 各有 11种优秀的拆分,S_{3,14}S3,14 有22 种优秀的拆分,所以答案是 5+2=75+2=7。
对于全部的测试点,保证1≤T≤101≤T≤10。以下对数据的限制均是对于单组输入数据而言的,也就是说同一个测试点下的TT组数据均满足限制条件。
我们假定nn为字符串SS的长度,每个测试点的详细数据范围见下表:
题解
- 题目大意:给定一个字符串求把其拆成AABB的形式的方法数
- 那么考虑求出以每个点开始的AA和以每个点结束的BB,然后若两组刚好相邻就为一组
- 考虑枚举A串的长度i,然后每隔i个建立一个点,那么一个长度为i*2的AA串一定会经过两个点
- 我们需要求出相邻两个点往前拓展的lis和往后拓展的lcp,组合之后可以得到一个A串
-
- 这样的话,我们可以确定从一段区间的开始都可以得到一个 AA串
-
代码
1 #include2 #include 3 #include 4 #define ll long long 5 using namespace std; 6 const int N=50010,mo=30000007; 7 int n,l,r,mid,head,tail,k,w,T; 8 char s[N]; 9 ll hash[N],p[N],x[N],y[N],ans; 10 ll get(int l,int r) { return ((hash[l]-hash[r]*p[r-l])%mo+mo)%mo; }11 int main()12 {13 scanf("%d",&T),p[0]=1; for (int i=1;i<=30000;i++) p[i]=p[i-1]*31%mo;14 while(T--) 15 {16 scanf("%s",s+1),n=strlen(s+1),ans=0,memset(x,0,sizeof(x)),memset(y,0,sizeof(y));17 hash[n+1]=0; for (int i=n;i>=1;i--) hash[i]=(hash[i+1]*31+s[i]-48+1)%mo;18 for (int i=1;i*2<=n;i++)19 for (int j=i*2;j<=n;j+=i)20 if (s[j]==s[j-i])21 {22 l=1,r=i,k=j-i,w=0;23 while (l<=r)24 {25 int mid=l+r>>1;26 if (get(k-mid+1,k+1)==get(j-mid+1,j+1)) l=mid+1,w=mid; else r=mid-1;27 }28 head=j-w+1,l=1,r=i,w=0;29 while (l<=r)30 {31 int mid=l+r>>1;32 if (get(k,k+mid)==get(j,j+mid)) l=mid+1,w=mid; else r=mid-1;33 }34 tail=j+w-1,head=max(head+i-1,j),tail=min(tail,j+i-1);35 if (head<=tail) x[head-i*2+1]++,x[tail+1-i*2+1]--,y[head]++,y[tail+1]--;36 }37 38 ans=0;39 for (int i=1;i<=n;i++) x[i]+=x[i-1],y[i]+=y[i-1];40 for (int i=1;i