题目描述：给一个字符串，如abab，它的前缀有a，ab，aba，abab，第一个前缀在字串中出现次数为2，第二个为2，第三个和第四个都为1，其和为6.给一个字符串，求和。

  方法：只要对每个位置i求出前面能匹配的以str[i]结尾的前缀的个数，用dp[i]表示前缀0...i - 1出现的次数

  即dp[next[i]] = dp[i],保证了不会重复，且具有传递性，dp[next[next[i]]] = dp[next[i]也自然包括了dp[i]。

首先对串做kmp，获得next函数，next[i]的真正意义所在 s[i-next[i] 1,i]==s[0,next[i]-1]
那么我们可以从后往前，不断回溯，把后面出现的模式往前累加，即dp[next[i]-1] =dp[i];初始dp值全设为1，因为从开始到i都是自身一个匹配。

代码：#include<iostream>
#include<string>
using namespace std;
char x[200005];
int next[200005];
int dp[200005];
int cnt;
void GetNext(int len)
{
    int i = 0, j = -1;
    next[0] = -1;
    while(i < len)
        if (j == -1 || x[i] == x[j])
        {
            i , j ;
            next[i] = j;
        }
        else
            j = next[j];
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        cnt = 0;
        int len1;
        scanf("%d", &len1);
        scanf("%s", x);
        GetNext(len1 1);
        for(int i = 1; i <= len1; i )
            dp[i] = 1;
        for(int i = len1 ; i >= 0; i--)
            if (next[i] != -1 && next[i] != 0)
                dp[next[i]] = dp[i];
        for(int i = 1; i <= len1; i )
        {
            cnt = dp[i];
            if (cnt >= 10007)
                cnt %= 10007;
        }
        printf("%d\n", cnt);
    }
}