多模式串匹配概念
多模式串匹配哭懈，即多個(gè)模式串在一個(gè)主串中進(jìn)行匹配唤冈。
雖然單模式串也能完成多模式串的匹配，但每個(gè)模式串都需要與主串進(jìn)行匹配银伟，如果遇到主串太長(zhǎng)的情況你虹，效率不高。
而多模式串匹配彤避，只需要掃描一次主串傅物，大大提高效率。
有一種經(jīng)典的多模式串匹配算法 -- AC 自動(dòng)機(jī)琉预，全稱(chēng)是 Aho-Corasick 算法董饰。下面來(lái)介紹其實(shí)現(xiàn)。
AC 自動(dòng)機(jī)
AC 自動(dòng)機(jī)在 Trie 樹(shù)的基礎(chǔ)上圆米，增加了類(lèi)似 KMP 的 next 數(shù)組卒暂，即每個(gè)節(jié)點(diǎn)會(huì)有個(gè) fail 指針，指向某個(gè)節(jié)點(diǎn)娄帖。數(shù)據(jù)結(jié)構(gòu)如下：
class ACNode {
var data: Character
// 字符集 26 個(gè)小寫(xiě)字母
var children: [ACNode?]
var isEnd: Bool = false
var fail: ACNode? = nil
var len: Int = 0
init(_ data: Character) {
self.data = data
children = [ACNode]()
// 初始化 26 個(gè)
var i = 0
while i < 26 {
children.append(nil)
i += 1
}
}
}
準(zhǔn)備工作
- 將多個(gè)模式串構(gòu)建成
Trie樹(shù) - 構(gòu)建
fail指針
構(gòu)建 Trie 樹(shù)
參考 Trie 樹(shù) 的文章也祠。
構(gòu)建 fail 指針
fail 指針的生成類(lèi)似于 KMP 中的next 數(shù)組計(jì)算方式，基于前一個(gè)值來(lái)計(jì)算近速。
fail 指針的定義
每個(gè)節(jié)點(diǎn)都有 fail 指針诈嘿。假設(shè)節(jié)點(diǎn)為 p，當(dāng)前串 str 為 root 到 p 的節(jié)點(diǎn)路徑削葱，找到其與所有模式串前綴匹配的最長(zhǎng)后綴子串奖亚，那么 fail 就指向所匹配前綴的最后一個(gè)字符節(jié)點(diǎn)。
后綴子串：不包括開(kāi)頭字符的子串析砸。
這里需要注意的是最長(zhǎng)后綴子串昔字，比如當(dāng)前串為 abc，模式串為 bc首繁、c作郭。雖然其與 bc、c 都匹配蛮瞄，但最長(zhǎng)的后綴子串是 bc所坯。
其中root.fail = NULL，若p是root的直接子節(jié)點(diǎn)挂捅，則p.fail = root芹助。
fail 指針的生成方法
假設(shè)當(dāng)前節(jié)點(diǎn)為 p，p.fail = q闲先，pc 記為 p 的某個(gè)子節(jié)點(diǎn)状土，qc 記為 q 的某個(gè)子節(jié)點(diǎn)。
- 若
pc == qc伺糠，則pc.fail = qc蒙谓。如下圖所示：
- 若
pc != qc，則不斷循環(huán)q = q.fail训桶，直到找到q的子節(jié)點(diǎn)與pc相等累驮，或者q == root結(jié)束酣倾。但如果q == root，則說(shuō)明沒(méi)有后綴與模式串的前綴匹配谤专，此時(shí)則令pc.fail = root躁锡。再繼續(xù)這兩個(gè)過(guò)程。
按照樹(shù)的廣度遍歷置侍，逐個(gè)生成節(jié)點(diǎn)的 fail 指針映之。
最終結(jié)果如下圖所示：
Swift 代碼如下：
// 構(gòu)建失敗指針
func buildFailPointer(_ root: ACNode) {
var queue = Array<ACNode>()
queue.append(root)
while !queue.isEmpty {
// 取出頭部
let p = queue.removeFirst()
// 遍歷其子節(jié)點(diǎn)
if !p.children.isEmpty {
for pc in p.children {
if let pc = pc {
// 如果父節(jié)點(diǎn)是 root，則 fail 指針直接指向 root
if p === root {
pc.fail = root
} else {
var q = p.fail
while q != nil {
// 如果 pc 在 q 的子節(jié)點(diǎn) 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)
}
}
}
}
}
模式串匹配
首先需要明確以下兩點(diǎn)：
-
若
p 的節(jié)點(diǎn)路徑 A ( root 到 p 的路徑)匹配主串秕衙，則p.fail的節(jié)點(diǎn)路徑B也是匹配的蠢甲。因?yàn)?A的后綴子串與B的前綴是相同的，所以前面肯定匹配灾梦，同理p.fail.fail的節(jié)點(diǎn)路徑也是峡钓。因此只需要不斷遍歷其
fail指針節(jié)點(diǎn)，判斷是否為結(jié)束符若河，如果是能岩，則該模式串就是匹配主串的。 在某條分支路徑上
A做匹配萧福，如果遇上不匹配的情況拉鹃，則切到其fail指針指向的另外一條分支B，再繼續(xù)匹配鲫忍。因?yàn)槠淝昂缶Y相同膏燕。
具體算法
逐個(gè)遍歷主串的字符，判斷該字符是否存在當(dāng)前節(jié)點(diǎn) p 的子節(jié)點(diǎn)中悟民。
- 如果存在坝辫，則
p指向其子節(jié)點(diǎn)，然后循環(huán)遍歷p鏈?zhǔn)降?fail指針指向的節(jié)點(diǎn)是否為模式串的結(jié)尾射亏，若是近忙，該模式串匹配完成。 - 如果不存在智润，則循環(huán)遍歷
fail的鏈?zhǔn)街羔樳M(jìn)行查找及舍，若沒(méi)找到，則節(jié)點(diǎn)p重新指回root窟绷。重復(fù)這 2 個(gè)步驟锯玛。
Swift 代碼如下：
// 進(jìn)行匹配
func match(_ text: String, _ root: ACNode) {
// 逐個(gè)遍歷主串
var p: ACNode? = root
var i = 0
while i < text.count {
let strIndex = text.index(text.startIndex, offsetBy: i)
let ch = text[strIndex]
// 判斷 p 的子節(jié)點(diǎn)是否匹配 ch，如果不匹配兼蜈，則往 fail 指針找
let index = indexOfChar(ch)
while p?.children[index] == nil && p !== root {
p = p?.fail
}
p = p?.children[index]
// 一直沒(méi)有匹配攘残，重新指回 root
if p == nil {
p = root
}
// 遍歷其 fail 指針拙友，找到結(jié)束的字符，即為匹配
var tmp = p
while tmp != nil {
if tmp!.isEnd {
print("match startPosition:\(i - tmp!.len + 1)")
}
tmp = tmp?.fail
}
i += 1
}
}
