字符串匹配算法
#算法 · #字符串 · #KMP · #BM · #Rabin-Karp · #AC自动机
字符串匹配是计算机科学中最基础的问题之一——在文本 T 中查找模式串 P 的所有出现位置。从暴力匹配到 KMP、Boyer-Moore、Rabin-Karp 再到 AC 自动机，每种算法都有独特的优化思路。
问题定义
给定文本 T[0..n-1] 和模式串 P[0..m-1]（n >> m）
找出 P 在 T 中所有出现的位置。
示例：
T = "ABABDABACDABABCABAB"
P = "ABABCABAB"
结果：位置 10算法对比
| 算法 | 预处理 | 匹配时间 | 最坏 | 空间 | 特点 |
|---|---|---|---|---|---|
| 暴力 | O(1) | O(n·m) | O(n·m) | O(1) | 最简单 |
| KMP | O(m) | O(n) | O(n) | O(m) | 永不回退文本指针 |
| Boyer-Moore | O(m+σ) | O(n/m) 最好 | O(n·m) | O(m+σ) | 实际最快 |
| Rabin-Karp | O(m) | O(n) 平均 | O(n·m) | O(1) | 多模式匹配 |
| AC 自动机 | O(L·σ) | O(n) | O(n) | O(L·σ) | 多模式匹配首选 |
1. KMP（Knuth-Morris-Pratt）
核心思想
利用已匹配的信息，失配时不回退文本指针，而是利用**前缀函数（next 数组）**回退模式串指针。
T: A B A B D A B A C D ...
P: A B A B C
√ √ √ √ ✗
暴力做法：P 整体右移 1 位，重新比较
KMP 做法：发现 "ABAB" 的前缀 "AB" 和后缀 "AB" 相同，
直接把 P 移动 2 位，从 'A' 继续比较前缀函数（next 数组）
go
// next[i] = P[0..i] 的最长相等前后缀长度
func buildNext(pattern string) []int {
m := len(pattern)
next := make([]int, m)
// next[0] = 0（单个字符的前缀函数为 0）
j := 0 // 前缀末尾
for i := 1; i < m; i++ {
// 失配时，回退 j
for j > 0 && pattern[i] != pattern[j] {
j = next[j-1]
}
if pattern[i] == pattern[j] {
j++
}
next[i] = j
}
return next
}
/*
示例：P = "ABABCABAB"
i: 0 1 2 3 4 5 6 7 8
P: A B A B C A B A B
next:0 0 1 2 0 1 2 3 4
*/KMP 匹配
go
func KMP(text, pattern string) []int {
n, m := len(text), len(pattern)
if m == 0 {
return nil
}
next := buildNext(pattern)
result := []int{}
j := 0 // 模式串指针
for i := 0; i < n; i++ {
// 失配时，利用 next 回退 j
for j > 0 && text[i] != pattern[j] {
j = next[j-1]
}
if text[i] == pattern[j] {
j++
}
if j == m {
result = append(result, i-m+1)
j = next[j-1] // 继续匹配
}
}
return result
}复杂度分析
- 预处理：O(m)，i 只增不减，j 每次最多回退 i 的增量
- 匹配：O(n)，同理 i 只增，j 回退次数有限
2. Boyer-Moore
核心思想
从右向左比较，利用坏字符规则和好后缀规则，一次跳过多位。
从右向左匹配：
T: H E R E I S A S I M P L E E X A M P L E
P: E X A M P L E
↑
从右开始坏字符规则
失配字符 b → 找 P 中 b 的最右出现位置 → 右移
T: ... A ...
P: ... B ... ← A ≠ B，在 P 左边找 'A'
A ... ← 找到！右移
如果左边没有，整个模式串移过失配位置好后缀规则
T: ... B C D E ...
P: ... B C D E ← 后缀 "BCDE" 已匹配，前面失配
好后缀 "BCDE" 在 P 前面也出现过 → 对齐
没出现过 → 找好后缀的最长后缀，在 P 前缀中出现过 → 对齐go
// BM 算法简化实现（仅坏字符规则）
func BM(text, pattern string) []int {
n, m := len(text), len(pattern)
if m == 0 {
return nil
}
// 坏字符表：记录每个字符在 pattern 中的最右位置
badChar := [256]int{}
for i := range badChar {
badChar[i] = -1
}
for i := 0; i < m; i++ {
badChar[pattern[i]] = i
}
result := []int{}
shift := 0
for shift <= n-m {
j := m - 1
// 从右向左比较
for j >= 0 && pattern[j] == text[shift+j] {
j--
}
if j < 0 {
result = append(result, shift)
// 整体右移 1 或好后缀规则
if shift+m < n {
shift += m - badChar[text[shift+m]]
} else {
shift++
}
} else {
// 坏字符规则
shift += max(1, j-badChar[text[shift+j]])
}
}
return result
}3. Rabin-Karp
核心思想
将字符串比较转为哈希值比较。用滚动哈希在 O(1) 内计算下一个窗口的哈希值。
T = "31415926"
P = "415"
Hash("314") → 不匹配
Hash("141") = (Hash("314") - 3*base²) * base + 1 → 滚动计算！
Hash("415") → 匹配！再逐字符验证
滚动哈希公式：
hash(i+1) = (hash(i) - T[i] * base^(m-1)) * base + T[i+m]go
func RabinKarp(text, pattern string) []int {
n, m := len(text), len(pattern)
if m == 0 || m > n {
return nil
}
base := 256 // 字符集大小
mod := 101 // 大质数取模（防溢出）
baseM := 1 // base^(m-1) % mod
// 计算 base^(m-1)
for i := 0; i < m-1; i++ {
baseM = (baseM * base) % mod
}
// 计算 pattern 的哈希值
patternHash := 0
for i := 0; i < m; i++ {
patternHash = (patternHash*base + int(pattern[i])) % mod
}
// 滑动窗口
textHash := 0
result := []int{}
for i := 0; i < n; i++ {
// 更新滚动哈希
if i >= m {
textHash = (textHash - int(text[i-m])*baseM) % mod
if textHash < 0 {
textHash += mod
}
}
textHash = (textHash*base + int(text[i])) % mod
// 哈希匹配 → 逐字符验证（防哈希碰撞）
if i >= m-1 && textHash == patternHash {
if text[i-m+1:i+1] == pattern {
result = append(result, i-m+1)
}
}
}
return result
}4. AC 自动机（Aho-Corasick）
核心思想
Trie + KMP 失败指针 = 多模式匹配利器。一次扫描文本，同时匹配所有模式串。
模式串集合：{"he", "she", "his", "hers"}
构建 Trie + 失败指针：
root
/ \
h s
/ \ \
e i h
/ \ \
r s e
/ \
s r
\
s
失败指针（→）：
- 每个节点的失败指针指向：当前路径的最长后缀（其他模式串的前缀）
- 如 "she" 的 'e' 失败 → 指向 "he" 的 'e'go
type ACNode struct {
children [26]*ACNode
fail *ACNode
isEnd bool
output []string // 该节点匹配的所有模式串
}
type AhoCorasick struct {
root *ACNode
}
func (ac *AhoCorasick) Insert(word string) {
node := ac.root
for _, ch := range word {
idx := ch - 'a'
if node.children[idx] == nil {
node.children[idx] = &ACNode{}
}
node = node.children[idx]
}
node.isEnd = true
node.output = append(node.output, word)
}
// BFS 构建失败指针
func (ac *AhoCorasick) BuildFailureLinks() {
queue := []*ACNode{}
// root 的直接子节点失败指针指向 root
for i := 0; i < 26; i++ {
if ac.root.children[i] != nil {
ac.root.children[i].fail = ac.root
queue = append(queue, ac.root.children[i])
}
}
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
for i := 0; i < 26; i++ {
if curr.children[i] == nil {
continue
}
child := curr.children[i]
// 设置 child 的失败指针
failNode := curr.fail
for failNode != nil && failNode.children[i] == nil {
failNode = failNode.fail
}
if failNode == nil {
child.fail = ac.root
} else {
child.fail = failNode.children[i]
// 合并 output
child.output = append(child.output, child.fail.output...)
}
queue = append(queue, child)
}
}
}
// 在文本中搜索所有匹配的模式串
func (ac *AhoCorasick) Search(text string) map[string][]int {
result := make(map[string][]int)
node := ac.root
for i, ch := range text {
idx := ch - 'a'
// 失配时跟随失败指针
for node != ac.root && node.children[idx] == nil {
node = node.fail
}
if node.children[idx] != nil {
node = node.children[idx]
}
// 检查该节点及其失败链上的所有匹配
for _, word := range node.output {
result[word] = append(result[word], i-len(word)+1)
}
}
return result
}应用场景
| 场景 | 说明 |
|---|---|
| 敏感词过滤 | 一次扫描匹配所有敏感词 |
| 搜索引擎 | 多关键词搜索 |
| 入侵检测 | Snort/ClamAV 使用 AC 自动机匹配攻击特征 |
| DNA 序列分析 | 匹配多个基因序列 |
| 输入法联想 | 多前缀匹配 |
算法选择决策
需要匹配的模式串数量？
单个模式串：
├── 文本较短 → 暴力匹配 / KMP
├── 文本很长，字符集小 → KMP
└── 文本很长，字符集大 → Boyer-Moore（实际最快）
多个模式串：
├── 模式串数量少（<10）→ Robin-Karp（多哈希）
└── 模式串数量多（≥10）→ AC 自动机后缀数组与后缀自动机
后缀数组（Suffix Array）
后缀数组是处理单个长文本的多种查询的神器——最长重复子串、最长公共子串、子串出现次数等。
定义：将字符串 S 的所有后缀按字典序排序后的起始索引数组。
S = "banana"
后缀列表:
0: banana
1: anana
2: nana
3: ana
4: na
5: a
排序后:
a → 起始索引 5
ana → 起始索引 3
anana → 起始索引 1
banana → 起始索引 0
na → 起始索引 4
nana → 起始索引 2
后缀数组 SA = [5, 3, 1, 0, 4, 2]
LCP 数组（Longest Common Prefix，相邻后缀的最长公共前缀）:
SA[0]="a", SA[1]="ana" → LCP = 1 ("a")
SA[1]="ana", SA[2]="anana" → LCP = 3 ("ana")
...
应用:
- 子串是否存在: 对 SA 二分查找 → O(|pattern| × log n)
- 最长重复子串: max(LCP[i]) → O(n)
- 两个串的最长公共子串: 拼接 + LCP → O(n)
- 不同子串个数: n(n+1)/2 - Σ LCP[i] → O(n)go
// 使用 O(n log n) 倍增法构建后缀数组
func buildSA(s string) []int {
n := len(s)
sa := make([]int, n)
rank := make([]int, n)
tmp := make([]int, n)
// 按单个字符排序
for i := 0; i < n; i++ {
sa[i] = i
rank[i] = int(s[i])
}
for k := 1; k < n; k <<= 1 {
sort.Slice(sa, func(i, j int) bool {
a, b := sa[i], sa[j]
if rank[a] != rank[b] {
return rank[a] < rank[b]
}
ra, rb := -1, -1
if a+k < n {
ra = rank[a+k]
}
if b+k < n {
rb = rank[b+k]
}
return ra < rb
})
tmp[sa[0]] = 0
for i := 1; i < n; i++ {
// ... 重新计算 rank ...
}
rank, tmp = tmp, rank
}
return sa
}正则表达式引擎原理：NFA → DFA
编程语言中的正则表达式底层都经历了"模式→NFA→DFA→匹配"的转换。
mermaid
flowchart LR
Pattern["正则表达式<br/>a(b|c)*d"] --> Parse["解析为 AST"]
Parse --> NFA["Thompson 构造<br/>→ ε-NFA"]
NFA --> DFA["子集构造<br/>→ DFA"]
DFA --> Minimize["Hopcroft 最小化<br/>→ 最小 DFA"]
Minimize --> Match["逐字符状态转移<br/>→ 匹配结果"]| 引擎类型 | 代表 | 算法 | 速度 | 回溯 | 反向引用 |
|---|---|---|---|---|---|
| DFA | grep, awk, RE2 | 子集构造 | ✅ 快 | ❌ 无 | ❌ 不支持 |
| NFA | PCRE, Java, Python | 回溯搜索 | 🟡 慢 | ✅ 有 | ✅ 支持 |
| Hybrid | V8 (Irregexp) | JIT NFA→DFA | ✅ 快 | 视情况 | 有限 |
关键：为什么 Go 的 regexp 保证线性时间？
Go 选择了 RE2 算法——纯 DFA 引擎，保证 O(n) 时间复杂度。代价是不支持反向引用（backreference）和零宽断言中某些变体。这是"安全性优先于功能"的设计选择。
go
// Go: 线性时间，但功能受限
re := regexp.MustCompile(`a(b|c)*d`)
re.MatchString("abcd") // O(n), 保证不爆炸
// Python/PCRE: 功能全，但可能在恶意输入下指数爆炸
// 这就是 ReDoS（正则表达式拒绝服务攻击）的根源
登录后即可发表评论 👇