【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了。。

 /* http://www.cnblogs.com/karl07/ */

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <cstdio>

 using namespace std;

 #define P 1000000007

 int T,fail[][],num,f[],Fail[];

 char s[];

 long long ans;

 void work(){

     scanf("%s",s+);

     f[]=,Fail[]=-,ans=;

     for (int i=;i<=;i++) fail[i][]=-;

     for (int i=,l=strlen(s+);i<=l;i++){

         Fail[i]=Fail[i-];

         while (s[Fail[i]+]!=s[i] && Fail[i]!=-) Fail[i]=Fail[Fail[i]];

         fail[][i]=++Fail[i];

         for (int j=;j<=;j++) fail[j][i]= fail[j-][i]==- ? - : fail[j-][fail[j-][i]];

         num=fail[][i];

         for (int j=;j>=;j--) fail[j][num]*>i ? num=fail[j][num] : ;

         if (num!= && num*>i) num=fail[][num];

         f[i]=f[Fail[i]]+;

         ans=(ans*(f[num]+))%P;

     }

     printf("%lld\n",ans);

 }

 int main(){

     scanf("%d\n",&T);

     while (T--) work();

     return ;

 }

奇怪的倍增

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

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

 /* http://www.cnblogs.com/karl07/ */

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <cstdio>

 using namespace std;

 #define P 1000000007

 int T,fail[],num,f[],Fail[];

 char s[];

 long long ans;

 void work(){

     scanf("%s",s+);

     f[]=,Fail[]=fail[]=-,ans=;

     for (int i=,l=strlen(s+);i<=l;i++){

         Fail[i]=Fail[i-];

         fail[i]=fail[i-];

         while (s[Fail[i]+]!=s[i] && Fail[i]!=-) Fail[i]=Fail[Fail[i]];

         while (s[fail[i]+]!=s[i] && fail[i]!=-) fail[i]=Fail[fail[i]];

         ++Fail[i];

         ++fail[i];

         while (fail[i]*>i) fail[i]=Fail[fail[i]];

         f[i]=f[Fail[i]]+;

         ans=(ans*(f[fail[i]]+))%P;

     }

     printf("%lld\n",ans);

 }

 int main(){

     scanf("%d\n",&T);

     while (T--) work();

     return ;

 }

正解