这道题我WA了好几遍，很平常的对于KMP的应用，一开始还T了，后来发现自己好像写了假的KMP，改了一下就A掉了，因为递归的话可能被卡成n^2，所以要递推出解，一种很巧妙的写法就可以直接递推出解（其实KMP本来就是这么写的。。）
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; #define mod 1000000007 #define N 1000005 int dp[N],t,next[N],n,num[N]; char s[N]; inline void KMP(long long ans=1) { n=strlen(s); next[0]=-1; int j; for (int i=0;i<n;i++) { j=next[i]; while (j!=-1&&s[i]!=s[j]) j=next[j]; next[i+1]=++j; num[i+1]=num[j]+1; } j=0; for (int i=1;i<n;i++) { while (j!=-1&&s[j]!=s[i]) j=next[j]; j++; while((j<<1)>i+1) j=next[j]; ans*=num[j]+1;ans%=mod; } cout<<ans<<endl; } int main(){ for(scanf("%d",&t);t--;) scanf("%s",s),num[0]=0,KMP(); return 0; }