哇，你造吗。。。蒟蒻当年NOI这道题。。。可是拿了0分哦~（废话这么多，你弱怪我啊！）
我们先kmp一次，记录下next数组及cnt数组，其中cnt表示他前面可以匹配的模式串个数。
然后在类似kmp的做一次，记录下Next数组，Next == next + 长度限制。
于是。。。ans = Π (cnt[Next[i]] + 1) (1 ≤ i ≤ len)
1 /************************************************************** 2 Problem: 3670 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:664 ms 7 Memory:13500 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 13 using namespace std; 14 typedef long long ll; 15 const int Len = 1000005; 16 const ll mod = 1000000007; 17 18 char st[Len]; 19 int len, next[Len], Next[Len], cnt[Len]; 20 ll ans; 21 22 inline void work_next() { 23 int i, t; 24 for (i = 1; i <= len; ++i) { 25 t = next[i - 1]; 26 while (t != -1 && st[i] != st[t + 1]) 27 t = next[t]; 28 next[i] = t + 1, cnt[i] = cnt[t + 1] + 1; 29 } 30 } 31 32 inline void work_Next() { 33 int i, t; 34 for (i = 1; i <= len; ++i) { 35 t = Next[i - 1]; 36 if (t * 2 + 2 > i) t = next[t]; 37 while (t != -1 && st[i] != st[t + 1]) 38 t = next[t]; 39 Next[i] = t + 1; 40 } 41 } 42 43 int main() { 44 int T, i; 45 scanf("%d ", &T); 46 while (T--) { 47 gets(st + 1), len = strlen(st + 1); 48 next[0] = Next[0] = -1; 49 work_next(); 50 work_Next(); 51 for (i = ans = 1; i <= len; ++i) 52 (ans *= (cnt[Next[i]] + 1)) %= mod; 53 printf("%lld ", ans); 54 } 55 }