欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - HDU3336
题意概括
给T组数据，每组数据给一个长度为n的字符串s。求字符串每个前缀出现的次数和，结果mod 10007。
题解
首先闭着眼睛KMP跑一跑。
然后我们来dp。
dp[i]表示以第i位结尾的前缀个数。
那么，根据Next的含义，不难写出dp[i]=dp[Next[i]]+1的转移方程式。
然后就OK了。
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=200005,mod=10007;
int T,n,Next[N],dp[N];
char str[N];
int main(){
scanf("%d",&T);
while (T--){
scanf("%d%s",&n,str+1);
memset(Next,0,sizeof Next);
int k=0;
for (int i=2;i<=n;i++){
while (k&&str[i]!=str[k+1])
k=Next[k];
if (str[i]==str[k+1])
k++;
Next[i]=k;
}
memset(dp,0,sizeof dp);
int ans=0;
for (int i=1;i<=n;i++){
dp[i]=dp[Next[i]]+1;
ans=(ans+dp[i])%mod;
}
printf("%d\n",ans);
}
return 0;
}