NOI | | hz2016Blog

[NOI2014]动物园
这题其实和前面有一题似乎在梦中见过的样子很像，只是这里要 $j*2>i$ 时跳fail而已。

#include<set>
#include<map>
#include<list>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define qread(x) x=read()
#define mes(x,y) memset(x,y,sizeof(x))
#define mpy(x,y) memcpy(x,y,sizeof(x))
#define Maxn 1000000
#define Mod 1000000007
#define INF 2147483647
inline long long read(){
    long long f=1,x=0;char ch;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
long long T,ans,n,num[Maxn+1],p[Maxn+1];
char s[Maxn+1];
long long kmp(){
    long long j=0;
    num[1]=1;
    for(int i=2;i<=n;i++){
        while(j>0&&s[j+1]!=s[i])j=p[j];
        if(s[j+1]==s[i])j++;
        p[i]=j;
        num[i]=num[j]+1;
    }
    j=0;ans=1;
    for(int i=2;i<=n;i++){
        while(j>0&&s[j+1]!=s[i])j=p[j];
        if(s[j+1]==s[i])j++;
        while(j*2>i)j=p[j];
        ans=(ans*(num[j]+1))%Mod;
    }
}
int main(){
    qread(T);
    while(T--){
        scanf("%s",s+1);n=strlen(s+1);
        kmp();
        printf("%d\n",ans);
    }
}

#include<set>

#include<map>

#include<list>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define qread(x) x=read()

#define mes(x,y) memset(x,y,sizeof(x))

#define mpy(x,y) memcpy(x,y,sizeof(x))

#define Maxn 1000000

#define Mod 1000000007

#define INF 2147483647

inline long long read(){

long long f=1,x=0;char ch;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return f*x;

}

long long T,ans,n,num[Maxn+1],p[Maxn+1];

char s[Maxn+1];

long long kmp(){

long long j=0;

num[1]=1;

for(int i=2;i<=n;i++){

while(j>0&&s[j+1]!=s[i])j=p[j];

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

p[i]=j;

num[i]=num[j]+1;

}

j=0;ans=1;

for(int i=2;i<=n;i++){

while(j>0&&s[j+1]!=s[i])j=p[j];

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

while(j*2>i)j=p[j];

ans=(ans*(num[j]+1))%Mod;

}

int main(){

qread(T);

while(T--){

scanf("%s",s+1);n=strlen(s+1);

kmp();

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

}