P2375 [NOI2014] 动物园

暴力怎么做，暴力是不是，kmp求next数组然后递归硬求。

考虑优化吧，首先，递归多少层完全可以记忆化，不，是直接预处理。

然后怎么跳？考虑我们已经处理完i点，跳到了j处，现在多了个i+1，怎么办？

是不是接着上一个跳就行？因为j的位置顶多移动一，如果j和i+1相等的话

这样就成了$O(n)$了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int n;
int mod=1000000007;
string s;
int ne[1000011];
int l;
int anss[1001001];
signed main(){
    read(n);
    while(n--){
        cin>>s;
        l=s.length();
        memset(ne,0,sizeof(ne));
        s=' '+s;
        int j=0;
        //anss[2]=1;
        anss[1]=1;
        anss[0]=0;
        for(int i=2;i<=l;++i){
            while(j&&s[i]!=s[j+1]) j=ne[j];
            if(s[i]==s[j+1])j++;
            ne[i]=j;
            anss[i]=anss[j]+1;
        }
        int ans=1;
        j=0;
        for(int i=2;i<=l;++i){
            while(j&&s[j+1]!=s[i]) j=ne[j];
            j+=(s[j+1]==s[i]);
            while((j<<1)>i) j=ne[j];
            ans=(ans*(anss[j]+1)%mod);
        }
        cout<<ans<<endl;
    }
    return 0;
}