记录编号	461293	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]动物园	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.355 s
提交时间	2017-10-19 19:29:42	内存使用	8.90 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define mod 1000000007
#define N 1000500
using namespace std;
int nxt[N],n,num[N],ans;
char a[N];
void getnext(){
	nxt[0]=-1; num[0]=1;
	for(int i=1,j=-1;i<n;i++){
		while(~j&&a[i]!=a[j+1])j=nxt[j];
		if(a[i]==a[j+1])j++;nxt[i]=j;
		if(j<0)num[i]=1;
		else num[i]=num[j]+1;
	}
	/*for(int i=0;i<n;i++)
		printf("%d  %d  %d\n",i,nxt[i],num[i]);*/
	ans=1;
	for(int i=1,j=-1;i<n;i++){
		while(~j&&a[i]!=a[j+1])j=nxt[j];
		if(a[i]==a[j+1])j++;
		while(~j&&(j+1)*2>(i+1))j=nxt[j];
		if(j>=0)ans=(1ll*ans*(num[j]+1))%mod;
	}
	printf("%d\n",ans);
}
int main(){
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%s",a);
		n=strlen(a);
		getnext();
	}
	return 0;
}
/*
3
aaaaa
ab
abcababc
*/