hdu3336 Count the string kmp+dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3336

很容易想到用kmp

这里是next数组的应用

定义dp[i]表示以s[i]结尾的前缀的总数

那么dp[i]=dp[next[i]]+1;

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int MAXN=200020;
 4 const int MOD=10007;
 5 int dp[MAXN];
 6 char str[MAXN];
 7 int next[MAXN];
 8 
 9 void getNext(char *p)
10 {
11     int j,k;
12     j=0;
13     k=-1;
14     next[0]=-1;
15     int len=strlen(p);
16     while(j<len)
17     {
18         if(k==-1||p[j]==p[k])
19         {
20             j++;
21             k++;
22             next[j]=k;
23         }
24         else k=next[k];
25     }
26 }
27 int main()
28 {
29     int T;
30     int n;
31     scanf("%d",&T);
32     while(T--)
33     {
34         scanf("%d",&n);
35         scanf("%s",&str);
36         getNext(str);
37         dp[0]=0;
38         int ans=0;
39         for(int i=1;i<=n;i++)
40         {
41             dp[i]=dp[next[i]]+1;
42             dp[i]%=MOD;
43             ans+=dp[i];
44             ans%=MOD;
45         }
46         printf("%d
",ans);
47     }
48     return 0;
49 }