[bzoj3670]动物园

发布时间：2020-12-16 10:48:47 所属栏目：百科来源：网络整理

导读：首先计算出 s 数组， s 表示可以重复的前缀等于后缀的个数，显然有s[i]=s[next[i]]+1 ，因为有且仅有 next 的 next 满足这个条件。然后直接暴力枚举所有 next ，直到它小于 i 的一半，这个时间复杂度就是o(n) 的 ? 1 #includebits/stdc++.h 2 using namespa

首先计算出s数组，s表示可以重复的前缀等于后缀的个数，显然有s[i]=s[next[i]]+1，因为有且仅有next的next满足这个条件。

然后直接暴力枚举所有next，直到它小于i的一半，这个时间复杂度就是o(n)的

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t,ans,k,sum[1000005],nex[1000005];
 4 char s[1000005];
 5 int main(){
 6     scanf("%d",&t);
 7     while (t--){
 8         scanf("%s",s);
 9         k=0;
10         memset(nex,0,sizeof(nex));
11         ans=sum[1]=1;
12         for(int i=1;s[i];i++){
13             while ((k)&&(s[k]!=s[i]))k=nex[k];
14             if (s[k]==s[i])k++;
15             nex[i+1]=k;
16             sum[i+1]=sum[k]+1;
17         }
18         k=0;
19         for(int i=1;s[i];i++){
20             while ((k)&&(s[k]!=s[i]))k=nex[k];
21             if (s[k]==s[i])k++;
22             while (2*k>i+1)k=nex[k];
23             ans=ans*(sum[k]+1LL)%1000000007;
24         }
25         printf("%dn",ans);
26     }
27 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!