Fork me on GitHub

[NOI-2011|BZOJ-2434] Ahri's Printer 阿狸的打字机 Fenwick树+AC自动姬

发表于 | 分类于
字数统计: 758字 | 阅读时长 ≈ 4分钟

题面

BZOJ-2434

分析

毒瘤题.

1.先考虑暴力的做法,对于每一个读进来的匹配串都建立一次AC自动d姬.

100%爆炸不加辣.似乎只能拿40分.

2.我们可以考虑出现重复计算的地方.有很大一部分的失配数组其实是没有变化的.但是我们无脑地把它破坏掉再重新建立起来,这部分的损耗很大.考虑优化中间的fail数组,我们在找适配节点的时候是不是只要往上面跳.插入这个节点的父节点就可以啦？做的时候记得大法师一遍.

这样拿70~80分.

3.在2的基础上加一个树状数组就行辣.

100分标算

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 1e5+5;
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
int n,m,cnt,T,l[SIZE],r[SIZE],t[200005];
int last[SIZE],lastq[SIZE],pos[SIZE],ans[SIZE];
char ch[SIZE];
struct fail_tree{
	int to,next,v;
}e[SIZE],que[SIZE];
inline void add(int x,int val){for(int i=x;i<=T;i+=i&-i)t[i]+=val;}
inline int query(int x){int sum=0;for(int i=x;i;i-=i&-i)sum+=t[i];return sum;}
void insert(int u,int v){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;}
struct Aho_Corasick{
	int cnt;
	int fa[SIZE],fail[SIZE],next[SIZE][26],q[SIZE];
	Aho_Corasick(){
		cnt=1;
		for(int i=0;i<26;i++)
			next[0][i]=1;
	}
	void build(){
		int now=1,id=0;
		for(int i=0;i<n;i++)
			if(ch[i]=='P')pos[++id]=now;
			else if(ch[i]=='B')now=fa[now];
			else 
			{
				if(!next[now][ch[i]-'a'])
				{
					next[now][ch[i]-'a']=++cnt;
					fa[cnt]=now;
				}
				now=next[now][ch[i]-'a'];
			}
	}
	void buildfail(){
		int head=0,tail=1;
		fail[1]=0;q[0]=1;
		while(head!=tail)
		{
			int now=q[head];head++;
			for(int i=0;i<26;i++)
				if(next[now][i])
				{
					int v=next[now][i];
					int k=fail[now];
					while(!next[k][i])k=fail[k];
					fail[v]=next[k][i];
					q[tail++]=v;
				}
		}
	}
	void solve()
	{
		int now=1,id=0;
		add(l[1],1);
		for(int i=0;ch[i];i++)
			if(ch[i]=='P')
			{
				id++;
				for(int x=lastq[id];x;x=que[x].next)
				{
					int t=pos[que[x].to];
					ans[x]=query(r[t])-query(l[t]-1);
				}
			}
			else if(ch[i]=='B')add(l[now],-1),now=fa[now];
			else now=next[now][ch[i]-'a'],add(l[now],1);;
	}	
}Aho_Corasick;
void dfs(int x)
{
	l[x]=++T;
	for(int i=last[x];i;i=e[i].next)
		dfs(e[i].to);
	r[x]=++T; //wtf!
}
void addedge(int x,int y,int z)
{
	que[z].next = lastq[y];
	lastq[y] = z;
	que[z].to = x;
}
int main(int argc, char *argv[])
{
	scanf("%s",ch);
	n=strlen(ch);
	Aho_Corasick.build();
	Aho_Corasick.buildfail();
	for(int i=1;i<=Aho_Corasick.cnt;i++)
		insert(Aho_Corasick.fail[i],i);
	m=read();
	for(int i=1;i<=m;i++)
    {
		int x=read(),y=read();
		addedge(x,y,i);
	}
	dfs(0);
	Aho_Corasick.solve();
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}