洛谷 P2375 [NOI2014]动物园

题目传送门

解题思路:

其实对于一个sum[i],其值就等于sum[next[i]] + sum[next[next[i]]] + ... + 1,然后我们可以记忆化,然后题目里又有一个限制,就是前后缀不能重合,那我们就找到最大但是不重合的那种情况,然后往小了枚举就好了.最后答案说要取模,所以不要忘了%%%ljx_xhy_yyq(排名无先后).

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define ljx_xhy_yyq 1000000007
 5 
 6 using namespace std;
 7 
 8 int n,sum[1000001],kmp[1000001];
 9 long long ans;
10 string p,l;
11 
12 int main() {
13     scanf("%d",&n);
14     while(n--) {
15         cin >> p;
16         l = " " + p;
17         int len = l.length() - 1,j = 0,u = 1;
18         ans = 1;
19         memset(sum,0,sizeof(sum));
20         sum[1] = 1;
21         for(int i = 2;i <= len; i++) {
22             while(j != 0 && l[i] != l[j+1]) j = kmp[j];
23             if(l[i] == l[j+1]) j++; 
24             kmp[i] = j;sum[i] = sum[j] + 1;
25         }
26         j = 0;
27         for(int i = 2;i <= len; i++) {
28             while(j != 0 && l[i] != l[j+1]) j = kmp[j];
29             if(l[i] == l[j+1]) j++;
30             while(j * 2 > i) j = kmp[j];
31             ans *= (long long)(sum[j]+1);
32             ans %= ljx_xhy_yyq;
33         }
34         printf("%lld
",ans);
35     }
36 
37     return 0;
38 }