【题意】
求一个字符串的num数组,表示1-i的即使前缀也是后缀且不重叠的串的个数
【分析】
考虑不断跳nxt数组,如nxt[i],nxt[nxt[i]]....
直到跳到长度小于i的一半的时候开始计数那么就得到了num数组
可是这样做的最坏时间复杂度仍然是$O(n^2)$,继续考虑优化,即减少重复递归
现在正常计算kmp时候顺便递推出ans数组,表示可以重复的弱化num个数
然后对于每个位置,利用nxt数组跳到可行的位置后,答案就为这个位置的ans值
【代码】
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll mod=1e9+7; const int maxn=1e6+6; int n,fail[maxn],ans[maxn]; ll cnt; char a[maxn]; int main() { freopen("zoo.in","r",stdin); freopen("zoo.out","w",stdout); int T; scanf("%d",&T); while(T--) { scanf("%s",a); n=strlen(a); int j=0; ans[0]=0;ans[1]=1; memset(fail,0,sizeof(fail)); for(int i=1;i<n;i++) { while(j && a[i]!=a[j]) j=fail[j]; if(a[i]==a[j]) j++; fail[i+1]=j; ans[i+1]=ans[j]+1; } // for(int i=1;i<n;i++) printf("%d ",ans[i]); j=0; cnt=1; for(int i=1;i<n;i++) { while(j && a[i]!=a[j] ) j=fail[j]; if(a[i]==a[j]) j++; while((j<<1)>(i+1)) j=fail[j]; cnt=(cnt*(ll)(ans[j]+1))%mod; } printf("%lld\n",cnt); } }