Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
对于一个字符串，我们可以写出这个字符串的所有非空前缀。例如“abab”，非空前缀有：“a”,“ab”，“aba”，“abab”。对于每一个前缀，我们可以计算出他在原字符串中出现的次数。所以我们可以看到，“a”在原字符串中出现了2次；
“ab”在原字符串中出现了2次；“aba”出现了1次；“abab”出现了一次。
现在，要求您计算出给定的字符串的所有非空前缀出现的次数之和。对于“abab”，答案就是2+2+1+1=6。
由于答案可能非常大，所以要求输出答案对10007取模的值。
Input
输入由2行组成；
第一行输入一个正整数n（n<=1000000），代表字符串的长度；
第二行输入一个长度为n的字符串，只由小写字母构成。
Output
输出由一行组成；
输出一个整数，代表给定的字符串的所有非空前缀出现的次数之和对10007取模的值。
Sample input and output
| Sample Input | Sample Output |
|---|---|
4 abab |
6 |
解题思路：kmp匹配算法求得next数组然后……..详细讲解kmp算法网址（http://blog.csdn.net/buaa_shang/article/details/9907183）
代码：
#include<cstdio>
#include<cstring>
int n;
const int maxn = 1000000+100;
char s[maxn];
int next[maxn];
void get_next(){next[1]=0;int i,j=0;for(i=2;i<=n;i++){while(j>0&&s[j+1]!=s[i]) { j=next[j];} if(s[j+1]==s[i]) {j+=1;}next[i]=j;}
}
int dp[maxn];
int main(){int t,i;scanf("%d",&n);scanf("%s",s+1);get_next();dp[0]=0;int sum=0;for(i=1;i<=n;i++){dp[i]=dp[next[i]]+1;sum=(sum+dp[i])%10007;}printf("%d\n",sum);return 0;
}