BZOJ 2434 阿狸的打字机

http://www.lydsy.com/JudgeOnline/problem.php?id=2434

思路:建立fail树，并找出dfs序，那剩下要做的就是每次找到一个串的位置，然后询问它的区间里面有多少我当前串的节点，具体做法见代码。

#include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<algorithm> #include<queue> struct edge{int to,next,id; }que[500005]; int fail[500005],sz,ch[500005][26],root,num,hw,low[500005],dfn[500005]; char s[500005]; int pos[500005],id,fi[500005],first[500005],next[500005],tot,go[500005]; int fa[500005],ans[500005],V[1000005],n,m; void insert(int x,int y){tot++;go[tot]=y;next[tot]=first[x];first[x]=tot; } void add(int x,int v){for (int i=x;i<=hw;i+=(i)&(-i)){V[i]+=v;} } int query(int x){int res=0;for (int i=x;i;i-=(i)&(-i)){res+=V[i];}return res; } void build(){int now=1;sz=1;for (int i=0;i<n;i++){if (s[i]=='P') pos[++id]=now;elseif (s[i]=='B') now=fa[now];else{int k=s[i]-'a';if (ch[now][k]==0) ch[now][k]=++sz,fa[sz]=now;now=ch[now][k];}} } void bfs(){std::queue<int>Q;for (int i=0;i<26;i++)if (!ch[root][i]) ch[root][i]=root;else if (ch[root][i]){fail[ch[root][i]]=root;Q.push(ch[root][i]);}while (!Q.empty()){int now=Q.front();Q.pop();for (int i=0;i<26;i++)if (!ch[now][i]){ch[now][i]=ch[fail[now]][i];}else{fail[ch[now][i]]=ch[fail[now]][i];Q.push(ch[now][i]);}} } void dfs(int x){dfn[x]=++hw;for (int i=first[x];i;i=next[i]){int pur=go[i];dfs(pur);}low[x]=++hw; } void solve(){add(dfn[1],1);//root节点也算上 int sx=0,now=1;for (int i=0;i<n;i++){if (s[i]=='P'){sx++;for (int j=fi[sx];j;j=que[j].next){int pur=pos[que[j].to];ans[que[j].id]+=query(low[pur])-query(dfn[pur]-1);}//询问dfs序区间里面有多少标记过的节点，有多少就代表y到root路径上的节点有多少能走到x的尾节点 }elseif (s[i]=='B') add(dfn[now],-1),now=fa[now];//删除的时候去掉 else{now=ch[now][s[i]-'a'];add(dfn[now],1);//走一步加一步 }} } int main(){scanf("%s",s);root=1;n=strlen(s);build();bfs();//建AC自动机 for (int i=1;i<=sz;i++)insert(fail[i],i);//建fail树 dfs(0);//找dfs序 scanf("%d",&m);for (int i=1;i<=m;i++){//把y相同的询问弄到一起 int x,y;scanf("%d%d",&x,&y);num++;que[num].to=x;que[num].next=fi[y];que[num].id=i;fi[y]=num;}solve();//统计答案 for (int i=1;i<=m;i++)printf("%d\n",ans[i]); }

 

转载于:https://www.cnblogs.com/qzqzgfy/p/5689086.html

总结

以上是生活随笔为你收集整理的BZOJ 2434 阿狸的打字机的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。