题解 CF235C 【Cyclical Quest】

asuldb

2019-01-20 07:31:34

Solution

厚颜无耻的发一篇可能是全网最劣解法 我们发现要求给定的串所有不同的循环同构出现的次数,可以直接暴力啊 因为一个长度为$n$的串,不同的循环同构次数显然是不会超过$n$的,所以我们可以直接对每一个循环通过分别求一下其出现次数 求其出现次数当然可以交给$SAM$来搞了 于是我们把所有的串都插入$SAM$里去,但是我们只计算$S$串产生的贡献,对于每一个$T$串我们要将其倍长之后再插入,这样我们就可以在$parent$树上直接树上倍增求出一个循环同构出现次数了 同时为了去重,我们每次跳出来一个循环同构之后给它打上标记,之后就不要再跳了 这样的做法当让是喜提$MLE$ 于是我们甚至可以直接那$map$来存边,之后不用树上倍增直接暴力往上跳,于是就能以全luogu最慢的好成绩通过这道题 代码 ```cpp #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<map> #include<vector> #define maxn 6000005 #define re register #define LL long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) std::map<int,int> son[maxn]; struct E{int v,nxt;}e[maxn]; int n,lst=1,cnt=1,num,m; int len[maxn],head[maxn],sz[maxn],deep[maxn],vis[maxn],fa[maxn]; inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;} void dfs(int x) {for(re int i=head[x];i;i=e[i].nxt) deep[e[i].v]=deep[x]+1,dfs(e[i].v),sz[x]+=sz[e[i].v];} int st[1000005],top; std::vector<int> a[100005]; int L[100005]; char S[1000005]; inline void ins(int c,int o,int t) { int f=lst,p=++cnt; lst=p; len[p]=len[f]+1; if(!o) sz[p]=1; if(o&&t) a[o].push_back(p); while(f&&!son[f][c]) son[f][c]=p,f=fa[f]; if(!f) {fa[p]=1;return;} int x=son[f][c]; if(len[f]+1==len[x]) {fa[p]=x;return;} int y=++cnt; len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y; for(std::map<int,int>::iterator it=son[x].begin();it!=son[x].end();it++) son[y].insert(*it); while(f&&son[f][c]==x) son[f][c]=y,f=fa[f]; } inline int find(int x,int li) {while(len[fa[x]]>=li) x=fa[x];return x;} int main() { scanf("%s",S+1),n=strlen(S+1);scanf("%d",&m); for(re int i=1;i<=n;i++) ins(S[i]-'a',0,0); for(re int i=1;i<=m;i++) { scanf("%s",S+1);L[i]=strlen(S+1);lst=1; for(re int j=1;j<L[i];j++) ins(S[j]-'a',i,0);ins(S[L[i]]-'a',i,1); for(re int j=1;j<L[i];j++) ins(S[j]-'a',i,1); } for(re int i=2;i<=cnt;i++) add(fa[i],i);deep[1]=1;dfs(1); for(re int i=1;i<=m;i++) { int ans=0;top=0; for(re int j=0;j<a[i].size();j++) { int t=find(a[i][j],L[i]); if(vis[t]) continue; st[++top]=t;ans+=sz[t];vis[t]=1; } printf("%d\n",ans); for(re int j=1;j<=top;j++) vis[st[j]]=0; } return 0; } ```