程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 235C. Cyclical Quest 後綴自動機

Codeforces 235C. Cyclical Quest 後綴自動機

編輯：C++入門知識

Codeforces 235C. Cyclical Quest 後綴自動機

將S建後綴自動機,對於每個串復制兩倍的長度(2L)在自動機上跑,

統計長度為L時,對應節點的出現次數

C. Cyclical Quest time limit per test 3 seconds memory limit per test 512 megabytes input standard input output standard output

Some days ago, WJMZBMR learned how to answer the query "how many times does a string x occur in a string s" quickly by preprocessing the string s. But now he wants to make it harder.

So he wants to ask "how many consecutive substrings of s are cyclical isomorphic to a given string x". You are given string s and n stringsxi, for each string xi find, how many consecutive substrings of s are cyclical isomorphic to xi.

Two strings are called cyclical isomorphic if one can rotate one string to get the other one. 'Rotate' here means 'to take some consecutive chars (maybe none) from the beginning of a string and put them back at the end of the string in the same order'. For example, string "abcde" can be rotated to string "deabc". We can take characters "abc" from the beginning and put them at the end of "de".

Input

The first line contains a non-empty string s. The length of string s is not greater than 106 characters.

The second line contains an integer n (1?≤?n?≤?105) — the number of queries. Then n lines follow: the i-th line contains the string xi — the string for the i-th query. The total length of xi is less than or equal to 106 characters.

In this problem, strings only consist of lowercase English letters.

Output

For each query xi print a single integer that shows how many consecutive substrings of s are cyclical isomorphic to xi. Print the answers to the queries in the order they are given in the input.

Sample test(s) input

baabaabaaa
5
a
ba
baa
aabaa
aaba

output

input

aabbaa
3
aa
aabb
abba

output

2
3
3

/* ***********************************************
Author        :CKboss
Created Time  :2015年06月16日 星期二 19時37分19秒
File Name     :CF235C.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

/************SAM****************/

const int CHAR=27,maxn=2000200;

struct SAM_Node
{
	SAM_Node *fa,*next[CHAR];
	int len,id,pos;
	SAM_Node(){}
	SAM_Node(int _len)
	{
		fa=0; len=_len;
		memset(next,0,sizeof(next));
	}
};

SAM_Node SAM_node[maxn],*SAM_root,*SAM_last;
int SAM_size;

SAM_Node *newSAM_Node(int len)
{
	SAM_node[SAM_size]=SAM_Node(len);
	SAM_node[SAM_size].id=SAM_size;
	return &SAM_node[SAM_size++];
}

SAM_Node *newSAM_Node(SAM_Node *p)
{
	SAM_node[SAM_size]=*p;
	SAM_node[SAM_size].id=SAM_size;
	return &SAM_node[SAM_size++];
}

void SAM_init()
{
	SAM_size=0;
	SAM_root=SAM_last=newSAM_Node(0);
	SAM_node[0].pos=0;
}

void SAM_add(int x,int len)
{
	SAM_Node *p=SAM_last,*np=newSAM_Node(p->len+1);
	np->pos=len; SAM_last=np;
	for(;p&&!p->next[x];p=p->fa) p->next[x]=np;
	if(!p) { np->fa=SAM_root; return ; }
	SAM_Node *q=p->next[x];
	if(q->len==p->len+1) { np->fa=q; return ; }
	SAM_Node *nq=newSAM_Node(q);
	nq->len=p->len+1;
	q->fa=nq; np->fa=nq;
	for(;p&&p->next[x]==q;p=p->fa) p->next[x]=nq;
}

/// !!!!!!!!!!!!! 統計每個節點出現的次數

int c[maxn],num[maxn];
SAM_Node* top[maxn];

void Count(char str[],int len)
{
	for(int i=0;ilen!=len;p=p->next[str[p->len]-'a']) num[p->id]=1; num[p->id]=1;

	for(int i=SAM_size-1;i>=0;i--)
	{
		p=top[i];
		if(p->fa)
		{
			SAM_Node *q=p->fa; num[q->id]+=num[p->id];
		}
	}
}

/************SAM****************/

char stmain[maxn],str[maxn];
int tn;
int vis[maxn];

int READ_STR(char *str)
{
	int i=0;
	char ch;
	while(true)
	{
		ch=getchar();
		if(ch=='\n') break;
		str[i++]=ch;
	}
	str[i]=0;
	return i;
}


int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int len=READ_STR(stmain);
	SAM_init();
	for(int i=0;ifa->len)
					cur=cur->fa;
			}

			int id=i;
			if(id>=n) id-=n;
			int to = str[id]-'a';
			while(cur!=0&&cur->next[to]==0)
			{
				cur=cur->fa;
				if(cur!=0) nowlen=cur->len;
			}
			if(cur!=0&&cur->next[to]!=0)
			{
				cur=cur->next[to];
				nowlen++;
			}
			else
			{
				cur=SAM_root;
				nowlen=0;
			}

			if(nowlen==n)
			{
				if(vis[cur->id]!=cas)
				{
					vis[cur->id]=cas;
					ans+=num[cur->id];
				}
			}
		}

		printf("%d\n",ans);
	}

    return 0;
}