1 4 abab
题意：给定一个字符串，求所有前缀的出现次数。
解题思路：首先求这个字符串的next数组，假如next值不为0，就代表与前面有匹配，累加，然后加上一个n，取模就得到了答案，
研究了好久，请教了好几个人才搞明白，太弱了。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-1 22:45:04
File Name :2.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=200100;
const double pi =acos(-1.0);
const double eps =1e-8;
const int mod=10007;
char str[maxn];
int next[maxn],dp[maxn];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int T,i,j,k,m,n;
cin>>T;
while(T--)
{
cin>>n;
scanf("%s",str);
j=0,k=-1;
next[0]=-1;
while(j<n)
{
if(k==-1||str[j]==str[k])
next[++j]=++k;
else k=next[k];
}
for(i=0;i<=n;i++)cout<<next[i]<<" ";cout<<endl;
for(i=0;i<n;i++)dp[i]=1;
int cnt=0;
for(i=1;i<=n;i++)if(next[i])cnt++;
cnt=(cnt+n)%mod;
cout<<cnt<<endl;
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18891685