多模式串匹配 - AC 自动机
多模式串匹配概念
多模式串匹配，即多个模式串在一个主串中进行匹配。
虽然单模式串也能完成多模式串的匹配，但每个模式串都需要与主串进行匹配，如果遇到主串太长的情况，效率不高。
而多模式串匹配，只需要扫描一次主串，大大提高效率。
有一种经典的多模式串匹配算法 -- AC 自动机，全称是 Aho-Corasick 算法。下面来介绍其实现。
AC 自动机
AC 自动机在 Trie 树的基础上，增加了类似 KMP 的 next 数组，即每个节点会有个 fail 指针，指向某个节点。数据结构如下：
class ACNode {
var data: Character
// 字符集 26 个小写字母
var children: [ACNode?]
var isEnd: Bool = false
var fail: ACNode? = nil
var len: Int = 0
init(_ data: Character) {
self.data = data
children = [ACNode]()
// 初始化 26 个
var i = 0
while i < 26 {
children.append(nil)
i += 1
}
}
}
准备工作
- 将多个模式串构建成
Trie树 - 构建
fail指针
构建 Trie 树
参考 Trie 树 的文章。
构建 fail 指针
fail 指针的生成类似于 KMP 中的next 数组计算方式，基于前一个值来计算。
fail 指针的定义
每个节点都有 fail 指针。假设节点为 p，当前串 str 为 root 到 p 的节点路径，找到其与所有模式串前缀匹配的最长后缀子串，那么 fail 就指向所匹配前缀的最后一个字符节点。
后缀子串：不包括开头字符的子串。
这里需要注意的是最长后缀子串，比如当前串为 abc，模式串为 bc、c。虽然其与 bc、c 都匹配，但最长的后缀子串是 bc。
其中root.fail = NULL，若p是root的直接子节点，则p.fail = root。
fail 指针的生成方法
假设当前节点为 p，p.fail = q，pc 记为 p 的某个子节点，qc 记为 q 的某个子节点。
- 若
pc == qc，则pc.fail = qc。如下图所示：
image.png
- 若
pc != qc，则不断循环q = q.fail，直到找到q的子节点与pc相等，或者q == root结束。但如果q == root，则说明没有后缀与模式串的前缀匹配，此时则令pc.fail = root。再继续这两个过程。
image.png
按照树的广度遍历，逐个生成节点的 fail 指针。
最终结果如下图所示：
image.png
Swift 代码如下：
// 构建失败指针
func buildFailPointer(_ root: ACNode) {
var queue = Array<ACNode>()
queue.append(root)
while !queue.isEmpty {
// 取出头部
let p = queue.removeFirst()
// 遍历其子节点
if !p.children.isEmpty {
for pc in p.children {
if let pc = pc {
// 如果父节点是 root，则 fail 指针直接指向 root
if p === root {
pc.fail = root
} else {
var q = p.fail
while q != nil {
// 如果 pc 在 q 的子节点 qc 中存在，则直接指向 qc
let index = indexOfChar(pc.data)
if (index >= 0 && index <= q!.children.count) {
if let qc = q!.children[index] {
pc.fail = qc
} else {
// 不存在，找 q 的 fail 指针
q = q!.fail
}
}
}
// 不存在，则指向 root
if q == nil {
pc.fail = root
}
}
queue.append(pc)
}
}
}
}
}
模式串匹配
首先需要明确以下两点：
-
若
p 的节点路径 A ( root 到 p 的路径)匹配主串，则p.fail的节点路径B也是匹配的。因为A的后缀子串与B的前缀是相同的，所以前面肯定匹配，同理p.fail.fail的节点路径也是。因此只需要不断遍历其
fail指针节点，判断是否为结束符，如果是，则该模式串就是匹配主串的。 -
在某条分支路径上
A做匹配，如果遇上不匹配的情况，则切到其fail指针指向的另外一条分支B，再继续匹配。因为其前后缀相同。
具体算法
逐个遍历主串的字符，判断该字符是否存在当前节点 p 的子节点中。
- 如果存在，则
p指向其子节点，然后循环遍历p链式的fail指针指向的节点是否为模式串的结尾，若是，该模式串匹配完成。 - 如果不存在，则循环遍历
fail的链式指针进行查找，若没找到，则节点p重新指回root。重复这 2 个步骤。
Swift 代码如下：
// 进行匹配
func match(_ text: String, _ root: ACNode) {
// 逐个遍历主串
var p: ACNode? = root
var i = 0
while i < text.count {
let strIndex = text.index(text.startIndex, offsetBy: i)
let ch = text[strIndex]
// 判断 p 的子节点是否匹配 ch，如果不匹配，则往 fail 指针找
let index = indexOfChar(ch)
while p?.children[index] == nil && p !== root {
p = p?.fail
}
p = p?.children[index]
// 一直没有匹配，重新指回 root
if p == nil {
p = root
}
// 遍历其 fail 指针，找到结束的字符，即为匹配
var tmp = p
while tmp != nil {
if tmp!.isEnd {
print("match startPosition:\(i - tmp!.len + 1)")
}
tmp = tmp?.fail
}
i += 1
}
}
