第一次学是 1 月份雅礼集训的时候……不过太久没用已经忘了= = 而且当时理解也不是很到位。
要省选了,得复习一下,顺便把坑填起来。
约定: $\Sigma$ 表示字符集大小,$T$ 为模板集合,$S$ 为母串,我们的目标是在母串中找出模板。
Trie
就是把各个字符串相同的前缀合并形成的树。比方说 $\mathtt{[“his”, “she”, “hers”, “is”]}$ 的 Trie 长这样:
把一个串插入 Trie 中代码如下。为了处理重复串, val[]
记录某个串在插入了 Trie 的串中出现了多少次。std::unordered_map<string, int> ms
用来记录每个串对应 Trie 中哪个点。
int sz, val[MAX_NODE+10], ch[MAX_NODE+10][SIGMA+10];
std::unordered_map<string, int> ms;
inline int idx(int c) { return c - 'a' + 1; }
void insert(char *str) {
int len = strlen(str), u = 0;
for(int i = 0; i < len; i++) {
int c = idx(str[i]);
// 建立新点,再向前走一步
if(!ch[u][c]) ch[u][c] = ++sz;
u = ch[u][c];
}
++val[u];
ms[string(str)] = u;
}
AC 自动机
用来在某个母串中找出出现的模板串。为了方便叙述,设 $S = \mathtt{“hishers”}$ 。
考虑在Trie上面行走,一个一个地匹配模板串。不能直接沿用在 Trie 中查找的过程,因为有2个问题摆在面前:
- 某个模板串 $T_i$ 的后缀是另一个模板串 $T_j$ 的前缀。这样的话匹配完成 $T_i$ 后, $T_j$ 也完成了部分的匹配,应该跳到 $T_j$ 看匹配完成没有。如 $T_i = \mathtt{“his”}, T_j = \mathtt{“she”}$ 。
- 某个模板串失配了,但是可能匹配上前缀相同的另一模板。如 $\mathtt{“his”}$ 和 $\mathtt{“hers”}$ 。
同时,上述 1 还有一种特例:
- 某个模板串 $T_i$ 的后缀等于另一个模板串 $T_j$ 。如 $\mathtt{“his”}$ 和 $\mathtt{“is”}$ 。
失配边
为了解决上面的问题,就要充分利用已匹配部分的信息。我们给 Trie 添加一些边来进行上述转移。
- 对于 1 ,从 $T_i$ 的结尾点向 $T_j$ 的相同前缀的结尾点连边
- 对于 2 ,从 $T_i$ 的失配点向 $T_j$ 当前匹配到的点连边(因为匹配 $T_i$ 的过程中 $T_j$ 也部分匹配)
上述两个对应的边集合称为失配边。特别地,如果不存在满足条件的 $T_j$ ,失配边指向 Trie 的根。
如图。为了清晰,只画出了部分失配边,且失配边指向根的均未画出。
不难想到,如果由浅到深逐层遍历 Trie ,第 $i$ 层的失配边可以由第 $i-1$ 层推出,即由图中黄色边推出绿色边:
同时为了加速匹配,我们维护后缀链接,即从某点出发,沿着失配边走,走到的第一个单词节点。
代码如下:
int f[MAX_NODE+10], last[MAX_NODE+10];
void get_fail() {
std::queue<int> Q;
for(int c = 1; c <= SIGMA; c++) if(ch[0][c]) {
int v = ch[0][c];
f[v] = last[v] = 0; Q.push(v);
}
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int c = 1; c <= SIGMA; c++) {
int v = ch[u][c];
if(!v) { ch[u][c] = ch[f[u]][c]; continue; } // 利用失配边信息,把不存在的边补上,见下文
Q.push(v);
int u2 = f[u];
while(u2 && !ch[u2][c]) u2 = f[u2];
f[v] = ch[u2][c];
last[v] = val[f[v]] ? f[v] : last[f[v]];
}
}
}
“把不存在的边补上”是怎么回事呢?考虑某个点没有母串当前位置字符对应儿子的情况,也就是不存在上图中下面一条蓝色边。在匹配的时候应该沿着s失配边,也就是左边的黄边走。为了避开这个过程,我们补上这条边,也就是连接左下角点到右上角点的边。这样走失配边的操作就可以省略了。
匹配
这个就不用解释了,沿着边走就可以了。也许当前点不是匹配点,但是后缀链接上有匹配点,要判断。注意:一定要先走一步再判断是否找到!!!不然最后一个位置无法匹配!!!
void found(int u) {
for(; u; u = last[u])
found_cnt[u] += val[u];
}
void search(char *str) {
int len = strlen(str), u = 0;
for(int i = 0; i < len; i++) {
int c = idx(str[i]);
u = ch[u][c];
if(val[u]) found(u);
else if(last[u]) found(last[u]);
}
}
例题
其实AC自动机不过就是个状态转移图而已,图论的玩法一般也都适用。
单串的多模式匹配这种板子题就不放了。
[POI2000]病毒
建立了AC自动机之后就是要判断有没有从0可以到达的环。sb的我最开始居然还在BFS……过了好久我才想起来有拓扑排序这种东西= = 拓扑排序即可。存在拓扑序输出 “NIE”,否则输出 “TAK”.
有向无环图存在拓扑序。如果无法找出拓扑序,说明图不是有向无环图。——刘汝佳《算法竞赛入门经典》
(以及编译输出文件名写成了源代码,直接把源代码覆盖了……重新打了一遍……省选的时候,一定不能犯这样的低级错误!写完了就用GUI备份一份,不要用rm,mv,cp
什么的!编译最好也别敲命令!用gedit的External Tool!)