洛谷P2375 [NOI2014]动物园

---恢复内容开始---
洛谷P2375 [NOI2014]动物园
KMP
 1 #include <bits/stdc++.h>
 2 #define LL long long
 3 #define GG int
 4 #define For(i, j, k) for(register int i=j; i<=k; i++)
 5 #define Dow(i, j, k) for(register int i=j; i>=k; i--)
 6 using namespace std;
 7 inline GG read() {
 8     GG x = 0, f = 1;
 9     char ch = getchar();
10     while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch = getchar(); }
11     while(ch>='0'&&ch<='9') { x = x*10+ch-48; ch = getchar(); }
12     return x * f;
13 }
14 
15 const int N = 1000011, mod = 1e9+7; 
16 int Q, len,ans; 
17 int nxt[N], num[N], cnt[N];  
18 char s[N]; 
19 
20 inline void kmp() {
21     nxt[1] = nxt[0] = 0; cnt[1] = 1; 
22     int x = 0; 
23     For(i, 2, len) {
24         while(x && s[i]!=s[x+1]) 
25             x = nxt[x]; 
26         if(s[i]==s[x+1]) ++x; 
27         nxt[i] = x; 
28         cnt[i] = cnt[nxt[i]]+1; 
29     }
30 }
31 
32 inline int work(int u, int alpha) {
33     if(u>alpha) return nxt[u] = work(nxt[u], alpha); 
34     return u;
35 }
36 
37 int main() {
38     Q=read(); 
39     while(Q--) {
40         ans = 1; 
41         scanf("%s", s+1); 
42         len = strlen(s+1); 
43         kmp();  
44         Dow(i, len, 1) 
45             num[i] = work(i, i/2);
46         For(i, 1, len) 
47             ans = 1ll*ans*(cnt[nxt[i]]+1) %mod; 
48         printf("%d
", ans); 
49     }
50 }
---恢复内容结束---