codeforces 235C Cyclical Quest

codeforces 235C Cyclical Quest

​​ 题意翻译 给一个主串和多个询问串，求询问串的所有样子不同的周期同构出现次数和

感谢@晰纹之洛 提供翻译

建后缀自动机 然后把询问串再复制一遍 然后每次在sam上跑的时候注意如果发现长度比我的n要大了 那么就需要跳到一个恰好大于等于我的位置上 这样的串最小 出现的次数最多 可以计数然后注意做过的地方需要打标记避免被重复统计

#include#define ll long longusing namespace std;const int N=1e6+10;char s[N];int ch[N<<1][26],len[N<<1],fa[N<<1],cnt=1,last=1,root=1,m,n,vis[N<<1],size[N<<1];int c[N],rk[N<<1],id;inline void insert1(int x){ int p=last,np=++cnt;len[np]=len[p]+1;size[np]=1; for (;p&&!ch[p][x];p=fa[p]) ch[p][x]=np; if (!p) fa[np]=root;else{ int q=ch[p][x]; if(len[p]+1==len[q]) fa[np]=q;else{ int nq=++cnt;fa[nq]=fa[q];memcpy(ch[nq],ch[q],sizeof(ch[q])); len[nq]=len[p]+1;fa[q]=fa[np]=nq; for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }last=np;}inline ll gao(){ int nn=n*2-1,now=1,l=0;ll ans=0; for (int i=1;i<=nn;++i){ int nxt=s[i]-'a'; if (ch[now][nxt]) now=ch[now][nxt],++l; else { while(now&&!ch[now][nxt]) now=fa[now]; if (!now) {l=0,now=1;continue;}else l=len[now]+1,now=ch[now][nxt]; } while(now!=1&&len[fa[now]]>=n) now=fa[now],l=len[now]; if(l>=n&&vis[now]!=id) ans+=size[now], vis[now]=id; }return ans;}int main(){ freopen("cf.in","r",stdin); scanf("%s",s+1);n=strlen(s+1);scanf("%d",&m); for (int i=1;s[i];++i) insert1(s[i]-'a'); for (int i=1;i<=cnt;++i) ++c[len[i]]; for (int i=1;i<=n;++i) c[i]+=c[i-1]; for (int i=1;i<=cnt;++i) rk[c[len[i]]--]=i; for (int i=cnt;i;--i) size[fa[rk[i]]]+=size[rk[i]]; for (int owo=1;owo<=m;++owo){ scanf("%s",s+1);n=strlen(s+1);id=owo; for (int i=1;i<=n;++i) s[i+n]=s[i]; printf("%I64d\n",gao()); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。