| 算法 | 核心思想 | 预处理时间 | 预处理空间 | 匹配时间复杂度（最好/平均/最坏） | 算法难度 | 优势 | 劣势 |
|---|---|---|---|---|---|---|---|
| 朴素 (Naïve) | 从左到右逐字符比较，失败后右移一位 | O(1) | O(1) | O(n) / O(n+m) / O(nm) | 极低 | 实现极其简单，无额外空间，短串时常因缓存友好而很快 | 最坏情况极慢（如文本和模式均为"aaaaa..."），无法利用任何跳过信息 |
| KMP | 前缀函数（π表）避免文本回溯 | O(m) | O(m) | O(n) / O(n) / O(n) | 中等 | 严格线性时间，最坏情况下也有保证；文本指针永不回溯，适合流式处理 | 需要O(m)额外空间；平均性能往往不如BM/Horspool等跳跃算法 |
| Boyer‑Moore (BM) | 从右向左比较，坏字符 + 好后缀双规则跳跃 | O(m+σ) | O(m+σ) | O(n/m) / O(n/m) / O(nm) | 复杂 | 平均性能极佳（尤其是大字母表、长模式串），跳跃步长很大 | 预处理较复杂，空间较大（σ表），最坏情况可能退化为O(nm)；对短模式串优势不明显 |
| Horspool (BMH) | BM的简化版，仅使用坏字符规则，且每次看窗口最后一个字符 | O(m+σ) | O(σ) | O(n) / 通常接近O(n/m) / O(nm) | 简单 | 实现简单，跳跃效果依然很好，实际应用中常比完整BM更快 | 最坏情况下仍可能退化为O(nm)；对于某些重复模式跳跃不如好后缀规则 |
| Sunday | 借鉴BM，但失败时看窗口下一个字符决定跳跃 | O(m+σ) | O(σ) | O(n) / 通常接近O(n/m) / O(nm) | 简单 | 跳跃更激进，平均性能甚至优于Horspool，短串表现优异 | 同样存在最坏退化；对大字母表需要构建跳转表 |
| Two‑Way | 关键分解 + 周期性跳跃，匹配时先扫右侧再扫左侧 | O(m) | O(1) | O(n) / O(n) / O(n) | 中等偏难 | O(n)最坏时间 + O(1)空间，完美平衡，被glibc/musl等标准库采用 | 实现比KMP复杂；平均跳跃不如BM系列激进；长模式串预处理稍慢 |
| Rabin‑Karp | 滚动哈希（如Rabin指纹）比较数值 | O(m) | O(1) | O(n) / O(n+m) / O(nm)（哈希冲突时） | 中等 | 适合多模式匹配（一次扫描匹配多个模式），可扩展至二维模式（矩阵） | 哈希冲突可能导致效率下降；需要谨慎设计哈希函数；最坏情况可能退化 |
| Aho‑Corasick | Trie + 失配指针（多模式版KMP） | O(总长度) | O(总长度) | O(n+z) | 复杂 | 一次性匹配所有模式，线性时间，工业级多模式匹配的标准解法 | 构建自动机时间/空间随模式数量线性增长；静态结构，动态增删模式困难 |
| Shift‑Or | 位并行，用bitset记录匹配状态 | O(m+σ) | O(m+σ)（或机器字） | O(n·⌈m/w⌉) (w为机器字长) | 中等 | 极快位运算，适合m≤64且字符集小的场景（如DNA）；天然支持模糊匹配（通配符） | 受机器字长限制，模式串长度通常不能超过64/128；需预先构建掩码表 |
| BNDM | 位并行 + 后缀自动机，从右向左扫描 | O(m+σ) | O(m+σ) | O(n·⌈m/w⌉) (最坏) / 平均接近O(n) | 中等偏难 | 对短模式串（m≤64）极快，尤其适合小字母表；比Shift‑Or跳跃更多 | 同样受字长限制；实现比Shift‑Or复杂 |
| Turbo‑BM | BM的改进，记忆已匹配后缀以减少重复比较 | O(m+σ) | O(m+σ) | O(n) / O(n) / O(n) | 复杂 | 保证了最坏情况线性时间，同时保留BM的平均高效 | 实现复杂，实际使用较少；仍需额外空间存储记忆信息 |
| Zhu‑Takaoka | 坏字符的二维扩展，考虑双字符 | O(m+σ²) | O(m+σ²) | 类似BM | 中等 | 跳跃距离更大（尤其在英文等字母表较大的环境） | 预处理时间和空间大幅增加（σ²），对短模式或无重复模式收益有限 |
| Bitap | 位并行 + 动态规划，支持模糊匹配（允许编辑距离） | O(m+σ) | O(m+σ) | O(n·⌈m/w⌉) | 中等 | 支持模糊匹配（近似字符串搜索），是UNIX agrep的命令基础 | 受字长限制；对长模式串需分块处理；性能随允许错误数增加而下降 |
| BOM (Backward Oracle Matching) | 构造因子自动机（Factor Oracle），从右向左扫描 | O(m) | O(m) | O(n) / O(n) / O(n²)（构造不佳时） | 复杂 | 最坏情况也有线性保证，平均跳跃长度大 | 自动机构造复杂；因子自动机概念较冷门，实际应用少 |
| Reverse Factor | 基于后缀自动机，从右向左匹配 | O(m) | O(m) | O(n) / O(n) / O(n) | 复杂 | 理论性能优异，最坏情况线性 | 自动机开销大，常数因子高，实际速度往往不如BM |
| Smith‑Waterman | 动态规划（局部序列比对） | O(m²) | O(m²) | O(nm) | 中等 | 生物信息学标准，允许插入、删除、替换，找最佳局部相似区域 | 二次时间，速度慢；只适用于专业领域，不适合通用字符串搜索 |
Created
June 9, 2026 08:39
-
-
Save CandyMi/6f0dda00a1ab0d1e202cec605fbc6a50 to your computer and use it in GitHub Desktop.
字符串匹配算法一览
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment