题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3670
题意概述：令num[i]表示字符串由1~i的字符形成的前缀中不相重叠的相同前后缀的数量，求mul{ num[i] | 1<=i<=L }mod1000000007。
实际上只要对KMP理解的好这就是个水题，可以想到dp求得num数组，num[i]=num[f[i]]+1，f[i]表示字符串的前缀1~i形成的不重叠的最长相同前后缀长度，如果f[i]=0的话就不存在。题目的提醒实际上很明显，想想KMP，发现这个也是一个用失配函数来匹配自己的过程。在推算f[i+1]的时候，先令j=f[i]，这样做直接保证了长度限制，并且如果可以匹配成功一定是最优的。然后在fail函数上匹配，直到成功为止。这个时候j后移一位，判断一下长度限制，如果不符合在fail上面再回跳一次。
主要是用到了fail函数一种理解方式：f[i]表示的是前i个字符最长相同前后缀长度。（这个前后缀是不包括原串的）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int maxn=;
const int mo=; int N,f1[maxn],f2[maxn],h[maxn];
char S[maxn]; void getfail(char *p)
{
int m=strlen(p);
f1[]=f1[]=;
for(int i=;i<m;i++){
int j=f1[i];
while(j&&p[j]!=p[i]) j=f1[j];
f1[i+]=p[j]==p[i]?j+:;
}
f2[]=f2[]=;
for(int i=;i<m;i++){
int j=f2[i];
while(j&&(p[j]!=p[i])) j=f1[j];
if(p[j]==p[i]) j++;
if(j*>i+) j=f1[j];
f2[i+]=j;
}
}
int main()
{
scanf("%d\n",&N);
for(int i=;i<=N;i++){
gets(S); getfail(S);
int n=strlen(S);
h[]=;
for(int i=;i<=n;i++) h[i]=h[f1[i]]+(f1[i]?:);
int ans=;
for(int i=;i<=n;i++) ans=(1ll*ans*(h[f2[i]]+(f2[i]?:)+))%mo;
printf("%d\n",ans);
}
return ;
}