首页 > 代码库 > BZOJ 2434 [Noi2011]阿狸的打字机（AC自动机）
BZOJ 2434 [Noi2011]阿狸的打字机（AC自动机）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2434
【题目大意】
给出一个打印的过程，‘a‘-‘z‘表示输入字母，P表示打印该字符串
B表示删去一个字符。问第x个打印的字符串在第y个打印的字符串中出现的次数
【题解】
我们根据打印的过程建立trie树，
当x是y的子串当且仅当y到根的链上有fail指针指向x的结尾，
而x在y中的出现次数则取决于有几个这样的指针，
我们根据fail指针建立fail树，按照fail树的dfs序进行统计，
在每个y处记录其要查询的x，在y点用树状数组对x点求dfs序区间和即可。
【代码】
#include <cstdio>#include <algorithm>#include <vector>#include <cstring> using namespace std;const int N=100010;int dfn,l[N],r[N],ans[N];vector<int> v[N],Q[N],ID[N];namespace BIT{ int c[N<<1]; //dfs void Initialize(){memset(c,0,sizeof(c));} void add(int x,int v){while(x<=dfn)c[x]+=v,x+=x&-x;} int query(int x){int res=0;while(x)res+=c[x],x-=x&-x;return res;}}namespace AC_DFA{ const int Csize=26; int id,tot,son[N][Csize],sum[N],f[N],fail[N],q[N],pos[N],match[N]; void Initialize(){ memset(sum,0,sizeof(int)*(tot+1)); memset(fail,0,sizeof(int)*(tot+1)); for(int i=0;i<=tot;i++)for(int j=0;j<Csize;j++)son[i][j]=0; tot=0; id=0; fail[0]=-1; } inline int Tr(char ch){return ch-‘a‘;} void Build(char *s){ int x=0; for(int l=strlen(s),i=0,w;i<l;i++){ if(s[i]==‘P‘)pos[++id]=x; else if(s[i]==‘B‘)x=f[x]; else{ if(!son[x][w=Tr(s[i])]){ son[x][w]=++tot; f[tot]=x; }x=son[x][w]; } } } void MakeFail(){ int h=1,t=0,i,j,x=0; for(i=0;i<Csize;i++)if(son[0][i])q[++t]=son[0][i]; while(h<=t)for(x=q[h++],i=0;i<Csize;i++) if(son[x][i]){ fail[son[x][i]]=son[fail[x]][i],q[++t]=son[x][i]; }else son[x][i]=son[fail[x]][i]; } void Solve(char *s){ using namespace BIT; BIT::Initialize(); int x=0,id=0; add(l[0],1); for(int L=strlen(s),i=0;i<L;i++){ if(s[i]==‘P‘){ id++; for(int k=0;k<Q[id].size();k++){ int u=pos[Q[id][k]]; ans[ID[id][k]]=query(r[u])-query(l[u]-1); } }else if(s[i]==‘B‘)add(l[x],-1),x=f[x]; else x=son[x][Tr(s[i])],add(l[x],1); } }}void Dfs(int x){ l[x]=++dfn; for(int i=0;i<v[x].size();i++)Dfs(v[x][i]); r[x]=++dfn;}char s[N];int main(){ using namespace AC_DFA; Initialize(); scanf("%s",s); Build(s); MakeFail(); for(int i=1;i<=tot;i++)v[fail[i]].push_back(i); int m,x,y; scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); Q[y].push_back(x); ID[y].push_back(i); }Dfs(0); Solve(s); for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0;}BZOJ 2434 [Noi2011]阿狸的打字机（AC自动机）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。