题意：给一个主串和多个询问串，求询问串的所有样子不同的周期同构出现次数和
没有周期同构很简单就是询问串出现次数，|Right|
有了周期同构，就是所有循环，把询问串复制一遍贴到后面啊！思想和POJ1509相似，不要局限于复制主串
然后走的时候维护nowLen
需要支持尾部插入字符(走转移边)和首部删除字符(走parent边)就行了
PS：家里上CF太慢了还是学校网速快
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; #define lc x<<1 #define rc x<<1|1 #define mid ((l+r)>>1) #define lson lc,l,mid #define rson rc,mid+1,r const int N=2e6+5; typedef long long ll; int n,ri[N]; char s[N]; struct node{ int ch[26],par,val; }t[N]; int sz=1,root=1,last=1; void extend(int c){ int p=last,np=++sz; t[np].val=t[p].val+1; ri[np]++; for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np; if(!p) t[np].par=root; else{ int q=t[p].ch[c]; if(t[q].val==t[p].val+1) t[np].par=q; else{ int nq=++sz; t[nq]=t[q];t[nq].val=t[p].val+1; t[q].par=t[np].par=nq; for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq; } } last=np; } int vis[N]; void walk(int id){//puts("walk"); int u=root,len=n+n-1,ans=0,nowLen=0; for(int i=1;i<=len;i++){ int c=s[i]-'a'; if(t[u].ch[c]) u=t[u].ch[c],nowLen++; else{ while(u&&!t[u].ch[c]) u=t[u].par; if(!u) u=root,nowLen=0; else nowLen=t[u].val+1,u=t[u].ch[c]; } //printf("i %d %d %d %d ",i,c,u,nowLen); if(vis[u]!=id&&nowLen>=n) vis[u]=id,ans+=ri[u];//,printf("ans %d %d ",u,ri[u]); if(n!=1) while(t[t[u].par].val+1>=n) u=t[u].par,nowLen=t[u].val; //printf("nowu %d ",u); } printf("%d ",ans); } int c[N],a[N]; void RadixSort(){ for(int i=1;i<=sz;i++) c[t[i].val]++; for(int i=1;i<=n;i++) c[i]+=c[i-1]; for(int i=sz;i>=1;i--) a[c[t[i].val]--]=i; } void solve(){ RadixSort(); int u; for(int i=sz;i>=1;i--) u=a[i],ri[t[u].par]+=ri[u]; int m;scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<n;i++) s[i+n]=s[i]; walk(i); } } int main(){ //freopen("in","r",stdin); scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++) extend(s[i]-'a'); solve(); }