[NOI2014]动物园
这题其实和前面有一题似乎在梦中见过的样子很像,只是这里要时跳fail而已。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#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); } } |