半年前看这题还感觉很神仙，做不动（没看题解）。
现在过来看发现……这tm就是一个sb题……
首先题面已经提示我们用 KMP 了。那 KMP 究竟能干啥呢？
看 $num$ 的定义。发现对于前缀 $i$，$nxt[nxt[dots nxt[i]]]$ 这个长度的前缀和后缀是相等的。
那么令 $cnt[i]=cnt[nxt[i]]+1$（其中 $cnt[0]=0$，也就是说在 $nxt$ 上跳能跳多少步），如果不考虑前缀后缀不重叠的限制，$num[i]=cnt[i]$。
那么限制怎么弄呢？其实就是要计算 $nxt[nxt[dots nxt[i]]]le lfloor i/2 floor$ 的个数。
令 $pt[i]$ 为 $lelfloor i/2 floor$ 中最大的 $nxt[nxt[dots nxt[i]]]$。那么 $num[i]=cnt[pt[i]]$。
可以用倍增做到 $O(nlog n)$。然而根本不用这么麻烦。
显然有 $pt[nxt[i]]le pt[i]$。那么我们倒着做，求出 $pt[i]$ 之后，令 $pt[nxt[i]]=pt[i]$。每次求解 $pt[i]$ 时，不停跳 $nxt$ 直到合法为止。
根据 KMP 的复杂度分析可得复杂度为 $O(n)$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1000100,mod=1000000007; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ int x=0,f=0;char ch=getchar(); while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } int t,n,nxt[maxn],cnt[maxn],pt[maxn]; char s[maxn]; int main(){ t=read(); while(t--){ scanf("%s",s+1); n=strlen(s+1); MEM(nxt,0);MEM(cnt,0);MEM(pt,-1); int j=nxt[1]=0; FOR(i,2,n){ while(j && s[i]!=s[j+1]) j=nxt[j]; if(s[i]==s[j+1]) j++; nxt[i]=j; } FOR(i,1,n) cnt[i]=cnt[nxt[i]]+1; ROF(i,n,1){ if(pt[i]==-1) pt[i]=i; while(pt[i]>i/2) pt[i]=nxt[pt[i]]; pt[nxt[i]]=pt[i]; } int ans=1; FOR(i,1,n) ans=1ll*ans*(cnt[pt[i]]+1)%mod; printf("%d ",ans); } }