HDU 3336

题目链接：

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

题目描述：

　　给定一个字符串，问该字符串的所有前缀在该字符串出现的次数之和。

　　比如说字符串"abab"，它的前缀分别是"a", "ab", "aba", "abab", 其中"a"在原字符串"abab"中出现了两次，同理"ab"出现了两次，"aba"出现了一次，"abab"出现了一次，所以总的出现次数之和就是六啦。

解题思路：

　　同样运用了next数组原理，同时还需要记忆化搜索一番。dp[i]表示以str[i]为结尾的字符串前缀之和，这里的dp转换思想跟next数组生成的思想是一样的，dp[i] = dp[next[i]] + 1。

　　如果想要更详细的了解可以看一下这篇博客，讲得很详细：http://972169909-qq-com.iteye.com/blog/1114968

代码：

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <map>
 6 #include <vector>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 #define ll long long
11 #define INF 0x3f3f3f3f3f
12 #define MAX 200200
13 #define MOD 10007
14 
15 int fail[MAX], dp[MAX];
16 
17 void getFail(char *str)
18 {
19     fail[0] = -1;
20     int k = -1, j = 0;
21     int len = strlen(str);
22     while(j < len) {
23         if(k == -1 || str[j] == str[k]) {
24             j++; k++;
25             fail[j] = k;
26         }
27         else
28             k = fail[k];
29     }
30 }
31 
32 int main()
33 {
34     //freopen("debug\in.txt", "r", stdin);
35     //freopen("CON", "w", stdout);
36     int i, j, k;
37     int test, n;
38     scanf("%d", &test);
39     while(test--) {
40         char str[MAX];
41         scanf("%d%s", &n, str);
42         getFail(str);
43         dp[0] = 0;
44         int ans = 0;
45         for(i = 1; i <= n; ++i) {
46             dp[i] = dp[fail[i]] + 1;
47             ans += dp[i];
48             ans %= MOD;
49         }
50         printf("%d
", ans);
51     }
52     return 0;
53 }