hdu 3336

http://acm.hdu.edu.cn/showproblem.php?pid=3336

题意：给一个字符串，问你这个字符串的前缀在这个字符串出现的次数

思路：先对字符串求一次next数组，然后枚举每一个终点，它的前缀其实对于它的next[len]进行递归寻找，知道他的next[len]为0，那么递归的次数也就是它的前缀出现的次数

然后这个我们其实可以用dp来做，也就是dp[i] = dp[next[i]] +1

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int mod = 10007;
 4 
 5 char str[200050];
 6 int n;
 7 int num[200050];
 8 int next[200050];
 9 char tmp[200050];
10 
11 
12 void getnext()
13 {
14     next[0] = -1;
15     int i = 0,j = -1;
16     while(i<n)
17     {
18         if(j==-1||str[i]==str[j])
19             next[++i]=++j;
20         else
21             j = next[j];
22     }
23 }
24 
25 int main()
26 {
27     int t;
28     scanf("%d",&t);
29     while(t--)
30     {
31         scanf("%d",&n);
32         scanf("%s",str);
33         memset(num,0,sizeof(num));
34         memset(next,0,sizeof(next));
35         getnext();
36         int ans = 0;
37         for(int i = 1;i<=n;i++)
38         {
39             num[i] = num[next[i]] +1;
40             ans = (ans+num[i])%mod;
41         }
42         printf("%d
",ans);
43     }
44     return 0;
45 }