Count the string(前缀出现次数

题目描述：

题意：

输出所有s中前缀在s中出现的次数。

思路：

拿到这题刚开始的时候我是没有头绪的。当然，DP问题本来就是一个玄学，再加上这题还得用到KMP算法对字符串进行处理，很难想到用DP去求解(是我太菜了QAQ)，我们用dp[i]表示i前面所出现的前缀重复的次数，因为KMP算法中next数组的定义，next[i]就是在i前面前缀重复的上一个位置，这个说法可能不怎么好理解，这里小编再做一个详细的解释，就比如aabaabaabaab这个字符串，next[6] = 3,next[9] = 6,next[12] = 6，因为next数组表示的是前缀后缀最大匹配长度，所以如果i-next[i]就是前缀的长度，而next[i]的值就是在这个字符串中上一次重复到这个前缀的位置。说到这里可能有人要问小编，这有什么用呢？得到了这个我就可以写出一个状态转移方程了，dp[i] = dp[next[i]] + 1,DP问题从来都是玄学……想到了这里的话这道题就可以dp迭代一下子就完成了。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define end '\n'
#define IOS ios::sync_with_stdio(0)
int nxt[N],len=0,dp[N],mod=10007;
void get_next(string p) {
    int j = 0, k = -1;
    nxt[0] = -1;
    while (j < len)
        if (k == -1 || p[j] == p[k])
            nxt[++j] = ++k;
        else
            k = nxt[k];
}
int main() {
    string a;
    IOS;
    int t;
    cin >> t;
    while (t--) {
        cin >> len;
        cin >> a;
        get_next(a);
        memset(dp, 0, sizeof(dp));
        int sum = 0;
        for (int i = 1; i <= len; i++) {
            dp[i] = dp[nxt[i]] + 1;
            sum = (sum + dp[i]) % mod;
        }
        cout << sum << end;
    }
    return 0;
}