這道題我WA了好幾遍，很平常的對于KMP的應用，一開始還T了，后來發(fā)現(xiàn)自己好像寫了假的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;}新聞熱點
疑難解答
