[NOI2014]动物园（KMP，字符串）

半年前看这题还感觉很神仙，做不动（没看题解）。

现在过来看发现……这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\rfloor$ 的个数。

令 $pt[i]$ 为 $\le\lfloor i/2\rfloor$ 中最大的 $nxt[nxt[\dots nxt[i]]]$。那么 $num[i]=cnt[pt[i]]$。

可以用倍增做到 $O(n\log 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=,mod=;

#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=,f=;char ch=getchar();

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',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+);

        n=strlen(s+);

        MEM(nxt,);MEM(cnt,);MEM(pt,-);

        int j=nxt[]=;

        FOR(i,,n){

            while(j && s[i]!=s[j+]) j=nxt[j];

            if(s[i]==s[j+]) j++;

            nxt[i]=j;

        }

        FOR(i,,n) cnt[i]=cnt[nxt[i]]+;

        ROF(i,n,){

            if(pt[i]==-) pt[i]=i;

            while(pt[i]>i/) pt[i]=nxt[pt[i]];

            pt[nxt[i]]=pt[i];

        }

        int ans=;

        FOR(i,,n) ans=1ll*ans*(cnt[pt[i]]+)%mod;

        printf("%d\n",ans);

    }

}