【bzoj3670】: [Noi2014]动物园字符串-kmp-倍增

【bzoj3670】: [Noi2014]动物园

一开始想的是按照kmp把fail算出来的同时就可以递推求出第i位要f次可以跳到-1

然后把从x=i开始顺着fail走，走到fail[x]*2<i 然后ans*=f[fail[x]]+1 就好了？

但是发现显然会变成O(n^2) TLE。。

于是就想到了倍增fail[i][j]就是第i位顺着fail 跳了 2^j 的位置

好像很对的样子就把O(nlogn)的交了一发好像还是TLE了。。

我可能需要W（卡）Y（常）S（数）优化。。把fail[i][j] 换成第j位顺着fail跳了2^i 次

似乎一下快了好多然后4s AC了。。

 1 /* http://www.cnblogs.com/karl07/ */
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <cstdio>
 7 using namespace std;
 8 
 9 #define P 1000000007
10 int T,fail[21][1000005],num,f[1000005],Fail[1000005];
11 char s[1000005];
12 long long ans;
13 
14 void work(){
15     scanf("%s",s+1);
16     f[0]=0,Fail[0]=-1,ans=1; 
17     for (int i=0;i<=20;i++) fail[i][0]=-1;
18     for (int i=1,l=strlen(s+1);i<=l;i++){
19         Fail[i]=Fail[i-1];
20         while (s[Fail[i]+1]!=s[i] && Fail[i]!=-1) Fail[i]=Fail[Fail[i]];
21         fail[0][i]=++Fail[i];
22         for (int j=1;j<=20;j++) fail[j][i]= fail[j-1][i]==-1 ? -1 : fail[j-1][fail[j-1][i]];
23         num=fail[0][i];
24         for (int j=20;j>=0;j--) fail[j][num]*2>i ? num=fail[j][num] : 0;
25         if (num!=0 && num*2>i) num=fail[0][num];
26         f[i]=f[Fail[i]]+1;
27         ans=(ans*(f[num]+1))%P;
28     }
29     printf("%lld
",ans);
30 }
31 
32 int main(){
33     scanf("%d
",&T);
34     while (T--) work(); 
35     return 0;
36 }

奇怪的倍增

然后发现正解是维护fail1和fail2。。fail1一个是原来的fail，fail2[x]是fail1[x]跳到fail[x]*2<i的结果

其实fail2可以跟着fail1一起递推，初始值换一下就好了。。

 1 /* http://www.cnblogs.com/karl07/ */
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <cstdio>
 7 using namespace std;
 8 
 9 #define P 1000000007
10 int T,fail[1000005],num,f[1000005],Fail[1000005];
11 char s[1000005];
12 long long ans;
13 
14 void work(){
15     scanf("%s",s+1);
16     f[0]=0,Fail[0]=fail[0]=-1,ans=1; 
17     for (int i=1,l=strlen(s+1);i<=l;i++){
18         Fail[i]=Fail[i-1];
19         fail[i]=fail[i-1];
20         while (s[Fail[i]+1]!=s[i] && Fail[i]!=-1) Fail[i]=Fail[Fail[i]];
21         while (s[fail[i]+1]!=s[i] && fail[i]!=-1) fail[i]=Fail[fail[i]];
22         ++Fail[i];
23         ++fail[i];
24         while (fail[i]*2>i) fail[i]=Fail[fail[i]];
25         f[i]=f[Fail[i]]+1;
26         ans=(ans*(f[fail[i]]+1))%P;    
27     }
28     printf("%lld
",ans);
29 }
30 
31 int main(){
32     scanf("%d
",&T);
33     while (T--) work(); 
34     return 0;
35 }

正解

【bzoj3670】: [Noi2014]动物园 字符串-kmp-倍增

【bzoj3670】: [Noi2014]动物园字符串-kmp-倍增