将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 stringxoccur in a strings" quickly by preprocessing the strings. But now he wants to make it harder.
So he wants to ask "how many consecutive substrings ofsare cyclical isomorphic to a given stringx". You are given stringsandnstringsxi, for each stringxifind, how many consecutive substrings ofsare cyclical isomorphic toxi.
Two strings are calledcyclical isomorphicif 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 strings. The length of stringsis not greater than106characters.
The second line contains an integern(1≤n≤105) — the number of queries. Thennlines follow: thei-th line contains the stringxi— the string for thei-th query. The total length ofxiis less than or equal to106characters.
In this problem, strings only consist of lowercase English letters.
Output
For each queryxiprint a single integer that shows how many consecutive substrings ofsare cyclical isomorphic toxi. Print the answers to the queries in the order they are given in the input.
Sample test(s)
input
baabaabaaa5ababaaaabaaaaba
output
75735
input
aabbaa3aaaabbabba
output
233
/* ***********************************************Author:CKbossCreated Time :2015年06月16日 星期二 19时37分19秒File Name:CF235C.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>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;i<SAM_size;i++) c[SAM_node[i].len]++;for(int i=1;i<=len;i++) c[i]+=c[i-1];for(int i=0;i<SAM_size;i++) top[–c[SAM_node[i].len]]=&SAM_node[i];SAM_Node *p=SAM_root;for(;p->len!=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;i<len;i++) SAM_add(stmain[i]-'a',i+1);Count(stmain,len);scanf("%d",&tn);getchar();int cas=0;while(tn–){int ans=0;cas++;int n=READ_STR(str);SAM_Node* cur=SAM_root;int nowlen=0;for(int i=0;i<2*n-1;i++){if(nowlen==n){nowlen–;if(nowlen<=cur->fa->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;}
，自己不喜欢的人，可以报之以沉默微笑；
