题意：
对于一个字符串S，定义$num_i$表示满足$jleq frac{i}{2},S_{1cdots j}=S_{i-j+1cdots i}$的j的个数。
求$prod limits_{i=1}^{n}{(num_i +1)}$对$10^{9}+7$取模的值。T组数据。
$Tleq 5,nleq 10^{6}$。
题解：
（随手写了个$O(Tnlog{n})$发现它过了……）
考虑线性做法，令$pos_i$为最大的满足$jleq frac{i}{2},S_{1cdots j}=S_{i-j+1cdots i}$的j。
那么显然$num_i = dep(pos_i )$，其中$dep(u)$为点u在fail树上的深度。
考虑怎么求出$pos_i$，这里有一个结论：直接采用kmp的方式从$pos_{i-1}$递归即可。
证明：
- 若$pos_{i}<frac{i}{2}$，那么直接转移就能转移到。
- 若$pos_{i}=frac{i}{2}$，那么一开始的时候$pos_{i-1}+1$就匹配上了。
这证明实在是蠢，但正突出了我的弱智，这tm都没想到？
在这里也顺便给出一下kmp复杂度的证明：
显然kmp时一直指向$nxt_{i-1}$的指针j的移动次数决定了复杂度的上界。
我们不考虑j的左移，只考虑j的右移，显然j在每个i处可能右移1或0位。
注意到指针j的左移次数不可能大于指针j的右移次数（参考括号匹配即可），所以总移动次数至多2n次，复杂度$O(n)$。
回到本题，复杂度$O(Tn)$。
套路：
- 字符串，前后缀匹配，第i位的答案全部能由第i-1位转移而来$ ightarrow KMP$。
代码：
#include<bits/stdc++.h> #define maxn 1000005 #define maxm 500005 #define inf 0x7fffffff #define mod 1000000007 #define ll long long #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; ll nxt[maxn],dep[maxn],pos[maxn]; char str[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void calc(ll n){ nxt[1]=0,dep[1]=1; for(rint i=2;i<=n;i++){ rint j=nxt[i-1]; while(j && str[j+1]!=str[i]) j=nxt[j]; if(str[j+1]==str[i]) nxt[i]=j+1,dep[i]=dep[j+1]+1; else nxt[i]=0,dep[i]=1; //cout<<i<<" "<<dep[i]<<endl; } } int main(){ //freopen("zoo6.in","r",stdin); ll T=read(); while(T--){ scanf("%s",str+1); ll n=strlen(str+1),ans=1; calc(n); for(rint i=2;i<=n;i++){ int j=pos[i-1]; while(j && str[j+1]!=str[i]) j=nxt[j]; if(str[j+1]==str[i]) j++; while(j && j>i/2) j=nxt[j]; //cout<<i<<" "<<j<<endl; pos[i]=j,ans=ans*(dep[j]+1)%mod; } printf("%lld ",ans); } return 0; }