这道题我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 1000005int 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;}新闻热点
疑难解答
