[NOI2014]动物园

题解:

先求出可重复的nex[]和num[].然后再次做kmp时,对于一个位置i一直跳到失配位置j,且(j<<1)<=i,所以此时重叠的num[i]=此时的num[j]+1.

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<queue>
 8 #include<vector>
 9 #include<stack>
10 #define MAXN 1000010
11 #define RG register
12 #define LL long long int
13 using namespace std;
14 const int INF=1e9;
15 const int mod=1e9+7;
16 int T;
17 int n;
18 char s[MAXN];
19 int nex[MAXN],num[MAXN];
20 LL ans;
21 void work()
22 {
23   int j=0;ans=1;num[1]=1;
24   for(int i=2;i<=n;i++)
25     {
26       while(j>0&&s[j+1]!=s[i]) j=nex[j];
27       if(s[j+1]==s[i]) j++;
28       nex[i]=j;num[i]=num[j]+1;
29     }
30   j=0;
31   for(int i=2;i<=n;i++)
32     {
33       while(j>0&&s[j+1]!=s[i]) j=nex[j];
34       if(s[j+1]==s[i]) j++;
35       while((j<<1)>i&&nex[j]) j=nex[j];
36       ans=ans*(num[j]+1)%mod;
37     }
38 }
39 int main()
40 {
41   freopen("1.in","r",stdin);
42   scanf("%d",&T);
43   while(T--)
44     {
45       scanf("%s",s+1);n=strlen(s+1);
46       work();
47       printf("%lld
",ans);
48     }
49   return 0;
50 }