企业官网建设流程全解析

P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands 题解

思路

考虑映射，将基因库的字符串SiS_iSi​映射成Si#SiS_i\#S_iSi​#Si​的形式，对于询问P,QP,QP,Q映射成Q#PQ\#PQ#P的形式，那么就相当于问每个询问串在基因库中出现的次数，直接跑 AC 自动机多模匹配即可。

代码

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intn;intch[5000010][5],ed[5000010],fail[5000010],c[255],id;intip[100010];voidins(string s,intx){intp=0;for(inti=0;i<s.size();i++){intj=c[s[i]];if(!ch[p][j])ch[p][j]=++id;p=ch[p][j];}ip[x]=p;}intq[4100010],l=1,r;voidbuild(){for(inti=0;i<5;i++)if(ch[0][i])q[++r]=ch[0][i];while(l<=r){intx=q[l++];for(inti=0;i<5;i++){int&y=ch[x][i];if(!y)y=ch[fail[x]][i];elsefail[y]=ch[fail[x]][i],q[++r]=y;}}}vector<int>G[5000010];voidquery(string s){intp=0;for(inti=0;i<s.size();i++){intj=c[s[i]];p=ch[p][j];ed[p]++;}}voiddfs(intx){for(inty:G[x]){dfs(y);ed[x]+=ed[y];}}string s[100010];intmain(){ios::sync_with_stdio(0);cin.tie(0);c['A']=0;c['G']=1;c['U']=2;c['C']=3;c['#']=4;intq;cin>>n>>q;for(inti=1;i<=n;i++){cin>>s[i];s[i]=s[i]+"#"+s[i];//字符串映射}dfs(0);for(inti=1;i<=q;i++){string s,t;cin>>s>>t;s=t+"#"+s;//字符串映射ins(s,i);}build();//建AC自动机for(inti=1;i<=id;i++)G[fail[i]].push_back(i);for(inti=1;i<=n;i++)query(s[i]);//多模匹配dfs(0);for(inti=1;i<=q;i++){cout<<ed[ip[i]]<<'\n';}return0;}