计算字符串问题

问题：给你一个字符串，然后让你把所有的前缀给找出来，并把它们在字符串中的出现次数相加，输出这个和写出算法。

Input
The first line is a single integer T, indicating the number of test cases.
For each case, the first line is an integer n (1 <= n <= 200000), which is the length of string s. A line follows giving the string s. The characters in the strings are all lower-case letters.
 
Output
For each case, output only one number: the sum of the match times for all the prefixes of s mod 10007.

Sample Input
1
4
abab

Sample Output
6

回答：主要考察KMP算法运用

#include<cstdio>
#include<cstring>
int n,m;
char b[200010];
int p[200010];
void get_p(){
    p[1]=0;
    int i,j=0;
    for(i=2;i<=m;i++){
        while(j>0&&b[j+1]!=b[i]) j=p[j];
        if(b[j+1]==b[i]) j+=1;
        p[i]=j;
    }
}
int dp[200010];//dp【i】:以string[i]结尾的子串总共含前缀的数量
int main(){
    int t,i;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&m);
        scanf("%s",b+1);
        get_p();printf("%d ",p[9]);
        dp[0]=0;
        int sum=0;
        for(i=1;i<=m;i++){
             dp[i]=dp[p[i]]+1;
             sum=(sum+dp[i])%10007;
        }
        printf("%d ",sum);
    }

   return 0;
}