多模式串匹配概念

多模式串匹配，即多个模式串在一个主串中进行匹配。

虽然单模式串也能完成多模式串的匹配，但每个模式串都需要与主串进行匹配，如果遇到主串太长的情况，效率不高。

而多模式串匹配，只需要扫描一次主串，大大提高效率。

有一种经典的多模式串匹配算法 -- 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
    }
}