HDU 3336(KMP)

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

考查next数组的应用和理解~~~~

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int N = 200002;
 6 char str[N];
 7 int  next[N];
 8 
 9 void get_next(int len)
10 {
11     int i = 0;
12     int j = -1;
13     next[i] = -1;
14     while(i < len)
15     {
16         if(j == -1 || str[i] == str[j])
17         {
18             i++;
19             j++;
20             next[i] = j;
21         }
22         else
23         {
24             j = next[j];
25         }
26     }
27 }
28 
29 int main()
30 {
31     int t;
32     int len;
33     scanf("%d", &t);
34     while(t--)
35     {
36         scanf("%d", &len);
37         scanf("%s", str);
38         get_next(len);
39         int res = len + next[len];
40         for(int i = 0; i < len; i++)
41         {
42             if(next[i] > 0 && next[i] + 1 != next[i + 1])
43             {
44                 res += next[i];
45             }
46         }
47         printf("%d\n", res % 10007);
48     }
49     return 0;
50 }