记录编号	483575	评测结果	AAAAAAAAAA
题目名称	循环同构	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.758 s
提交时间	2018-01-17 21:44:05	内存使用	253.99 MiB

#include<bits/stdc++.h>
#define MAXN 2000010
using namespace std;
int N,n,np,S,tot,f[MAXN],t[MAXN][27],r[MAXN],len[MAXN];
void Insert(int x){
	int p=np;len[np=++tot]=len[p]+1;r[np]=1;
	while(p&&!t[p][x])t[p][x]=np,p=f[p];
	if(!p){f[np]=S;return;}
	int q=t[p][x];
	if(len[q]==len[p]+1)f[np]=q;
	else{
		int nq=++tot;
		memcpy(t[nq],t[q],sizeof(t[q]));
		f[nq]=f[q];len[nq]=len[p]+1;
		f[np]=f[q]=nq;
		while(p&&t[p][x]==q)t[p][x]=nq,p=f[p];
	} 
}
char ch[MAXN];
int sum[MAXN],id[MAXN],used[MAXN],ans;
int main(){
	freopen("rotate.in","r",stdin);
	freopen("rotate.out","w",stdout);
	scanf("%s",ch);
	n=strlen(ch);np=S=tot=1;
	for(int i=0;i<n;i++)Insert(ch[i]-'a');
	for(int i=1;i<=tot;i++)sum[len[i]]++;
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
	for(int i=1;i<=tot;i++)id[sum[len[i]]--]=i;
	for(int i=tot;i;i--)r[f[id[i]]]+=r[id[i]];
	scanf("%d",&N);
	while(N--){
		scanf("%s",ch);
		n=strlen(ch);ans=0;
		for(int i=0;i<n;i++)ch[i+n]=ch[i];
		int now=0,p=S;
		for(int i=0;i<(n<<1);i++){
			int x=ch[i]-'a';
			if(t[p][x])now++,p=t[p][x];
			else{
				while(p&&!t[p][x])p=f[p];
				if(!p)now=0,p=S;
				else now=len[p]+1,p=t[p][x];
			}
			if(now>=n){
				int tmp=p;
				while(tmp&&len[f[tmp]]>=n)tmp=f[tmp];
				if(used[tmp]!=N+1)used[tmp]=N+1,ans+=r[tmp];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}