记录编号	414517	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]动物园	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.337 s
提交时间	2017-06-14 15:23:45	内存使用	8.89 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mod 1000000007
const int M=1000000;
int t,last[M+10],num[M+10],len;
long long ans=1;
char s[M+10];
void getfail(){
     last[0]=last[1]=0;
     num[0]=-1;
     for(int i=2,k=0;i<=len;i++){
       while(k&&s[k]!=s[i-1]) k=last[k];
       if(s[k]==s[i-1]) k++;
       last[i]=k;
       num[i]=num[k]+1;
     }
}
long long getans(){
     for(int i=2,k=0;i<=len;i++){
       while(k&&s[k]!=s[i-1]) k=last[k];
       if(s[k]==s[i-1]) k++;
       while(k>(i>>1))
          k=last[k];
       ans=ans*(num[k]+2)%mod;
     }
     return ans;
}
int main(){
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout); 
    scanf("%d",&t);
    while(t--){
      ans=1;
      scanf("%s",s);
      len=strlen(s);
      getfail();
      printf("%lld\n",getans());
    }
    //while(1);
    return 0;
}