2434: [Noi2011]阿狸的打字机 - #include <Seter> - using namespace Orz;

2434: [Noi2011]阿狸的打字机

Seter posted @ 2012年1月25日 16:02 in BZOJ with tags Aho-Corasick SegTree , 3835 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2434

RunID User Problem Result Memory Time Language Code Length Submit Time
198975 Seter 2434 Accepted 20760 kb 352 ms C/Edit 1562 B 2012-02-03 14:26:54

做了4小时……最后发现问题在于我的AC自动机模板是错的……一直没怀疑……555这么弱怎么活……

不过最后1Y+Rank1,代码长度也是最短的(DYH大神1.9KB+),还是比较满意的结果!

这题同时考察了AC自动机和维护DFS序两个点,如果你对AC自动机理解得好的话一下子就能看出怎么做。同时ymNOI虐场的CLJ大神……

首先粗略地介绍一下AC自动机,这是一个在字母表较小的情况下线性的多串匹配算法。把所有目标串构成一个trie树,对于每个节点,记录一个fail指针表示如果匹配失败,则最近能跳到哪里。比如x的fail指向y,则说明root..x这个字符串的后缀是根..y,且对于所有root..x的后缀,root..y是最长的一个在trie中的。

构出trie后,点x的fail指针可以通过它父亲f的fail指针算出来。假设x对应字符c,依次检查f->fail,f->fail->fail,f->fail->fail->fail……root,如果有一个存在字符为c的儿子t,则x->fail=t,否则x->fail=root,这个还是很好想的……

问题在于处理顺序,我就是这里2X了。正确方法应该是弄个队列,一开始只有root,每次处理完一个点后把这个点所有儿子加进来即可。至于为什么……呃……不知道 T^T


对于这题,先构出AC自动机。然后对于一个询问(x,y),暴力的做法是,枚举root..y上的每一个点作为终点(即这个点为最后一个字符),不断取fail指针,如果能跳到x,则说明这个位置匹配成功,这个应该很好理解。

考虑能跳到x的节点,如果将fail指针反过来,这就是一棵树,叫做fail tree。在fail tree中,能跳到x的节点就是x的子树节点!只要找出这些节点中root..y中的节点有几个就可以了。

离线查询子树信息可以用DFS序来做,一个点的子树在DFS序中是一段,可以用BIT等维护,不说了。遍历整个trie,当询问到节点y时,对于每个询问(x,y),我们需要知道在fail tree中,x的子树节点中有几个是在root..y中的。即在遍历到y时,BIT中保存的是root..y这些节点的信息,这些点每个点的值是1,其它点是0。那么只要遍历一个点的儿子之前将其设为1,遍历完改回0就可以了,询问即是询问一段的和。

如果不懂的话先自己想想……也可以在下面留言恩。这个还是比较麻烦的,我想了好久,最重要的是要注意,这里有trie和fail tree两个树,其中trie是用来遍历和构造fail指针的,fail tree只需要记录它的DFS序,然后更新都是在DFS序上做手脚。

 

#include <stdio.h>
#define maxn 100010
#define T struct trie
#define E struct edge
#define Q struct qz
T{T*f,*fail,*c[26];int id}t,stt[maxn],*que[maxn]={&t};
E{E*next;int y}*map[maxn],st[maxn];
Q{Q*next;int x,ans}*q[maxn],stq[maxn];
int id[maxn],s[maxn][2],n,a[maxn],bq=-1,eq=1;
char str[2000000],*p=str;
inline void I(x,y){for(;x<=n;x+=x&-x)a[x]+=y;}
inline S(x){int t=0;for(;x;x-=x&-x)t+=a[x];return t;}
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}void Init(x){E*p=map[x];for(s[x][0]=++n;p;p=p->next)Init(p->y);s[x][1]=n;}
void Travel(T*x){
	Q*p=q[x->id];int i=-1;
	for(;p;p=p->next)p->ans=S(s[p->x][1])-S(s[p->x][0]-1);
	while(++i!=26)if(x->c[i]){
		I(s[x->c[i]->id][0],1);
		Travel(x->c[i]);
		I(s[x->c[i]->id][0],-1);
	}
}main(){
	int m=1,i=0,y;T*f=&t;fread(p,1,2000000,stdin);p--;
	while(*++p>0)if(*p=='P')id[i++]=f->id;
	else if(*p=='B')f=f->f;
	else if(*p<'a'||*p>'z')break;
	else if(f->c[y=*p-'a'])f=f->c[y];
	else(f->c[y]=stt+m)->f=f,(f=f->c[y])->id=m++;
	while(++bq!=eq)for(i=-1;++i!=26;)if(que[bq]->c[i]){
		for(f=que[bq]->fail;f&&!f->c[i];)f=f->fail;
		f=(que[eq]=que[bq]->c[i])->fail=f?f->c[i]:&t;
		st[eq].y=que[eq]->id;st[eq].next=map[f->id];map[f->id]=st+eq++;
	}for(Init(0),i=m=getint();i--;q[y]=stq+i){
		stq[i].x=id[getint()-1];
		stq[i].next=q[y=id[getint()-1]];
	}for(Travel(&t);m--;)printf("%d\n",stq[m].ans);
	return 0;
}

 

By Seter

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee