记录编号	285532	评测结果	AAAAAAAAAA
题目名称	循环同构	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	1.486 s
提交时间	2016-07-22 21:23:30	内存使用	246.36 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=2000010;
int fa[maxn],len[maxn],rit[maxn],w[maxn],sa[maxn];
int n,Q,cnt,lst,ch[maxn][26],vis[maxn];
char s[maxn];
struct SAM{
	SAM(){
		memset(fa,0,sizeof(fa));
		memset(len,0,sizeof(len));
		memset(rit,0,sizeof(rit));
		cnt=lst=1;
	}
	
	void Insert(int c){
		int p=lst,np=lst=++cnt;len[np]=len[p]+1;
		while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
		if(!p)fa[np]=1;
		else{
			int q=ch[p][c];
			if(len[p]+1==len[q])fa[np]=q;
			else{
				int nq=++cnt;len[nq]=len[p]+1;
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];
			}
		}
	}
	
	void Prepare(){
		rit[1]=1;
		for(int i=1,p=1;i<=n;i++)
			rit[p=ch[p][s[i]-'a']]+=1;
		for(int i=1;i<=cnt;i++)w[len[i]]+=1;
		for(int i=1;i<=cnt;i++)w[i]+=w[i-1];
		for(int i=1;i<=cnt;i++)sa[--w[len[i]]]=i;
		for(int i=cnt;i;i--)rit[fa[sa[i]]]+=rit[sa[i]];
	}
	
	void Solve(int tim){
		scanf("%s",s+1);n=strlen(s+1);
		for(int i=1;i<=n;i++)s[n+i]=s[i];
		int p=1,ans=0,l=0;
		for(int i=1,c;i<=2*n;i++){
			c=s[i]-'a';
			while(p!=1&&!ch[p][c])
				{p=fa[p];l=len[p];}
			if(!ch[p][c])l=0;
			else{p=ch[p][c];l+=1;}
			
			if(l>=n){
				while(len[fa[p]]>=n)p=fa[p],l=len[p];
				if(vis[p]!=tim)vis[p]=tim,ans+=rit[p];
			}
		}
		printf("%d\n",ans);
	}
}sam;
int main(){
	freopen("rotate.in","r",stdin);
	freopen("rotate.out","w",stdout);
	scanf("%s%d",s+1,&Q);n=strlen(s+1);
	for(int i=1;i<=n;i++)sam.Insert(s[i]-'a');
	sam.Prepare();while(Q--)sam.Solve(Q+1);
	return 0;
}