Tang-Dreamoon's Blog

NOI 阿狸的打字机

发表于 | 分类于 ， ，

对AC自动机的深层次的理解

　　题目链接：bzoj 2434

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：这个题本质就是在问：给定一棵 Trie 树，询问根到 X 的字符串在根到 Y 的字符串中出现了多少次。而 X 在 Y 中出现（即是 Y 的一个子串），必定是 Y 的一个前缀的后缀。在 Trie 树中根到 Y 的路径上的点都是 Y 的前缀。在 Fail 树中根到点 P 的路径上的点都是 P 的后缀。离线做法，在 Trie 树上 DFS ，维护 Fail 树的 DFS 序列。根到 Trie 树上当前点的所有点沿 Fail 树到根的路径权值 +1。Fail 树到根的路径上的权值 +1，询问 Fail 树上的一个点权值，可以转化为点的权值 +1，询问子树内权值和。

　　我思故我在：通过这道题给我最大的启示是：Fail 指针的含义，对于一个串 X，即在所有的串中找到一个最长的前缀等于 X 的后缀(类似 Next 数组，但是并不一样)。又因为对于一个完整的字符串，它一定是 Trie 树上的一个前缀。所以如果我们不断的走一个前缀的 Fail 指针，那么我们将遍历到所有的对于它来说有价值的后缀。第二点，我发现我对于这道题所谓的离线理解并不正确。一开始我以为离线就是以 Y 串对 X 串进行分组，然后一个 Y 一个 Y 的进行 DFS 并维护树状数组。实则不然，这个题所谓的离线是指在建完AC自动机并维护完 DFS 序后，再次将读入都读进来一遍，然后一边读入、一边维护树状数组。原题中的三个操作就变成了在树状数组上插入、删除和查询的操作。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,m;
int tot=0,sum=0,yyy=0;
char ap[100100];
int map[100100][30];
int fa[100100];
int bi[100100];
int fail[100100];
int shu[100100];
int where[100100];
int to[100100];
vector<int> ve[100100];
vector<int> pa[100100];
struct table{
	int l,r,id;
}tap[100100];
void trie()
{
	int now=0;
	for(int i=1;i<=n;i++)
	{
		if(ap[i]=='P')
		{
			sum++;
			bi[sum]=now;
		}
		else if(ap[i]=='B')
		{
			now=fa[now];
		}
		else
		{
			int x=ap[i]-'a';
			if(map[now][x]==0) map[now][x]=++tot,fa[tot]=now;
			now=map[now][x];
		}
	}
}
void ac()
{
	queue<int> q;
	q.push(0);fail[0]=0;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=0;i<26;i++)
		{
			if(map[x][i]!=0)
			{
				int j=fail[x];
				while(j!=0&&map[j][i]==0) j=fail[j];
				if(map[j][i]!=0&&map[j][i]!=map[x][i]) fail[map[x][i]]=map[j][i],ve[map[j][i]].push_back(map[x][i]);
				else fail[map[x][i]]=0,ve[0].push_back(map[x][i]);
				q.push(map[x][i]);
			}
		}
	}
}
void dfs(int x)
{
	for(int i=0;i<ve[x].size();i++)
	{
		int y=ve[x][i];
		where[y]=++yyy;
		dfs(y);
	}
	to[x]=yyy;
}
void add(int x,int y)
{
	for(int i=x;i<=yyy;i+=i&(-i))
		shu[i]+=y;
}
int ask(int x)
{
	if (x==0) return 0;
	int ans=0;
	for(int i=x;i>=1;i-=i&(-i))
		ans+=shu[i];
	return ans;
}
int main()
{
	scanf("%s",ap+1);
	n=strlen(ap+1);
	trie();
	ac();
	where[0]=++yyy;
	dfs(0);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		tap[i].l=x,tap[i].r=y;
		pa[y].push_back(x),tap[i].id=pa[y].size()-1;
	}
	sum=0;
	int now=0;
	for(int i=1;i<=n;i++)
	{
		if(ap[i]=='P')
		{
			sum++;
			for(int j=0;j<pa[sum].size();j++)
			{
				int x=pa[sum][j];
				pa[sum][j]=ask(to[bi[x]])-ask(where[bi[x]]-1);
			}
		}
		else if(ap[i]=='B')
		{
			add(where[now],-1);
			now=fa[now];
		}
		else
		{
			int x=ap[i]-'a';
			now=map[now][x];
			add(where[now],1);
		}
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",pa[tap[i].r][tap[i].id]);
	}
	return 0;
}