题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3670
第一次写KMP算法...又T又WA了半天...
1. num 数组表示包括其本身的前缀后缀相同个数，所以 num[1] = 1 ；
2.指针开两个，不要一个来回移动，不然会惨 T；
num 数组、nxt 数组的定义一定要搞清楚才行呢...
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; int const maxn=1000005; ll ans,mod=1e9+7; int n,nxt[maxn],num[maxn]; char a[maxn]; int rd() { int ret=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return ret*f; } int main() { n=rd(); while(n--) { // scanf("%s",&a+1); cin>>a+1; int l=strlen(a+1); memset(nxt,0,sizeof nxt); memset(num,0,sizeof num); ans=1; nxt[1]=0; num[1]=1;// int nw=0,nw2=0; for(int i=2;i<=l;i++) { // int nw=nxt[i-1]; while(a[i]!=a[nw+1]&&nw)nw=nxt[nw]; // if(nw==-1&&a[1]==a[i])nxt[i]=1; // else // nxt[i]=nw+1; // nw=nxt[i]; if(a[i]==a[nw+1])nw++; nxt[i]=nw; num[i]=num[nw]+1; // printf("num[%d]=%d ",i,num[i]); // printf("nxt[%d]=%d ",i,nxt[i]); while(a[i]!=a[nw2+1]&&nw2)nw2=nxt[nw2]; if(a[i]==a[nw2+1])nw2++; while(nw2*2>i) { // if(nw*2<=i) // { // num[i]=num[nw]+1;break; // } // cout<<nw<<endl; nw2=nxt[nw2]; } // printf("i:%d num=%d ",i,num[i]); (ans*=(num[nw2]+1))%=mod; } printf("%lld ",ans); } return 0; }