首页 > 代码库 > BZOJ2434 NOI2011 阿狸的打字机 AC自动机+树状数组+DFS序
BZOJ2434 NOI2011 阿狸的打字机 AC自动机+树状数组+DFS序
题意：给定三个操作：1、在当前字符串的末尾添加一个字符c 2、在当前字符串的末尾删除一个字符 3、记录当前字符串并对其标号。再给出N组询问，每组询问需回答第x个字符串在第y个字符串中出现的次数
题解：
首先按照如下规则建Trie，设当前节点为t，第i个字符串的结尾在Trie中的位置为mark[i]：
1、插入操作：看t是否有c这个儿子，有则t=t->child[c]，否则t->child[c]=NewNode,t=t->child[c]
2、删除操作：t=t->father
3、标号操作：mark[i]=t,i++
建好Trie之后构造fail指针，那么对于每个询问(x,y)，答案就是Trie中从mar[y]到根的路径中，有多少个节点经过一次或多次fail指针的转移能到达mark[x]。
考虑到fail指针都是由下到上且每个节点的出度均为1，所以我们按照逆fail指针建出逆fail树，那么问题就变成，在逆fail树的mark[x]的子树中，有多少个节点是在mark[y]到根的路径上，子树用DFS序跑出来.然后我们离线，将所有y相同的询问放在一起，用树状数组来维护以某个点为结尾的字符串是否出现过，重新读一遍所有的操作：
1、插入操作：将t所在节点在DFS序上位置的值+1，t=t->child[S[i]-‘a‘]
2、删除操作：将t所在节点在DFS序上位置的值-1，t=t->f
3、标号操作：查询t有关的询问的答案
#include <queue>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define lowbit(x) (x&(-x))const int MAXK=26;const int MAXN=100000+2;struct HASH{ int x,id; HASH *next; HASH(){} HASH(int _x,int _id,HASH *_next):x(_x),id(_id),next(_next){}}*table[MAXN],mem[MAXN];struct Trie{ int id,mark; Trie *child[MAXK],*f,*fail; vector<Trie *> next;}*root;int M,N=1,cnt,ans[MAXN],BIT[MAXN],l[MAXN],r[MAXN];char S[MAXN];queue<Trie *> q;Trie *NewNode(Trie *f){ Trie *x=new Trie; memset(x,0,sizeof(Trie)); x->f=f; return x;}void Get_Fail(Trie *&x){ for(int i=0;i<MAXK;i++) if(x->child[i]){ x->child[i]->fail=x,q.push(x->child[i]); x->next.push_back(x->child[i]); } Trie *p,*t; while(!q.empty()){ t=q.front(),q.pop(),N++; for(int i=0;i<MAXK;i++) if(t->child[i]){ p=t->fail; while(p!=x && !p->child[i]) p=p->fail; if(p->child[i]) p=p->child[i]; t->child[i]->fail=p,p->next.push_back(t->child[i]); q.push(t->child[i]); } else t->child[i]=t->fail->child[i]; }}void DFS(Trie *&x){ x->id=++cnt; if(x->mark) l[x->mark]=cnt; for(int i=0;i<x->next.size();i++) DFS(x->next[i]); if(x->mark) r[x->mark]=cnt;}int Sum(int p){ int ret=0; while(p) ret+=BIT[p],p-=lowbit(p); return ret;}void Add(int p,int x){ while(p<=N) BIT[p]+=x,p+=lowbit(p);}int main(){ scanf("%s %d",S,&M); for(int i=1,x,y;i<=M;i++){ scanf("%d %d",&x,&y); table[y]=&(mem[cnt++]=HASH(x,i,table[y])); } Trie *t=root=NewNode(0); for(int i=0,j=0;S[i];i++) if(S[i]==‘P‘) t->mark=++j; else if(S[i]==‘B‘) t=t->f; else{ if(!t->child[S[i]-‘a‘]) t->child[S[i]-‘a‘]=NewNode(t); t=t->child[S[i]-‘a‘]; } cnt=0; Get_Fail(root),DFS(root); t=root; for(int i=0;S[i];i++) if(S[i]==‘P‘) for(HASH *p=table[t->mark];p;p=p->next) ans[p->id]=Sum(r[p->x])-Sum(l[p->x]-1); else if(S[i]==‘B‘) Add(t->id,-1),t=t->f; else t=t->child[S[i]-‘a‘],Add(t->id,1); for(int i=1;i<=M;i++) printf("%d\n",ans[i]); return 0;}
BZOJ2434 NOI2011 阿狸的打字机 AC自动机+树状数组+DFS序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。