记录编号	414291	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]动物园	最终得分	100
用户昵称	yymxw	是否通过	通过
代码语言	C++	运行时间	0.536 s
提交时间	2017-06-13 21:39:37	内存使用	16.53 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define p 1000000007
using namespace std;
long long n,l,shu;
long long fail[1000100],num[1000100];
char a[1000100];
void getfail1()
{
  fail[0]=fail[1]=0;
  num[1]=1;
  for(int i=2,k=0;i<=l;++i)
  {
    while(k&&a[k]!=a[i-1])
      k=fail[k];
    if(a[k]==a[i-1])
      ++k;
    fail[i]=k;
    num[i]=num[fail[i]]+1;
  }
}
void getfail2()
{
  for(int i=2,k=0;i<=l;++i)
  {
    while(k&&a[k]!=a[i-1])
      k=fail[k];
    if(a[k]==a[i-1])
      ++k;
    //fail[i]=k;
    while(k>(i/2))
      k=fail[k];
    shu=shu*(num[k]+1)%p;
  }
}
int main()
{
  freopen("zoo.in","r",stdin);
  freopen("zoo.out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n;++i)
  {
    shu=1;
    memset(fail,0,sizeof(fail));
    memset(num,0,sizeof(num));
    scanf("%s",a);
    l=strlen(a);
    getfail1();
    getfail2();
    printf("%lld\n",shu);
  }
  //system("pause");
  return 0;
}