字符串匹配
字符串匹配旨在查找文本中某个模式的所有出现位置；经典的算法会预处理模式，以跳过冗余比较，实现线性或次线性搜索时间。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
字符串匹配是指在文本中查找给定模式字符串所有出现位置的问题；精确字符串匹配算法会报告模式与文本子字符串完全对齐的每个偏移量。
Scope
本主题涵盖精确的单模式匹配算法——朴素方法、Knuth-Morris-Pratt、Boyer-Moore以及基于哈希的Rabin-Karp——以及使它们高效的预处理（失配函数、移位表、滚动哈希），以及通过Aho-Corasick自动机扩展到多模式匹配。近似匹配和基于索引的搜索在相关主题中介绍。
Core questions
- 为什么朴素匹配所需时间与模式和文本长度的乘积成正比？
- 预处理模式如何避免重新检查文本字符？
- Knuth-Morris-Pratt失配函数和Boyer-Moore移位规则如何工作？
- Rabin-Karp如何使用哈希快速测试对齐？
- 如何将匹配扩展到同时匹配多个模式？
Key concepts
- 朴素匹配
- Knuth-Morris-Pratt算法
- 失配函数
- Boyer-Moore算法
- 坏字符和好后缀规则
- Rabin-Karp算法
- 滚动哈希
- Aho-Corasick自动机
Key theories
- Knuth-Morris-Pratt失配函数
- 通过预先计算每个模式前缀的最长真前缀（同时也是后缀），Knuth-Morris-Pratt算法在失配后智能地移动模式，并且从不重新检查文本字符，从而实现线性时间匹配。
- Boyer-Moore从右到左扫描
- Boyer-Moore从模式的最后一个字符开始向后比较，并使用坏字符和好后缀规则跳过文本的大部分，在典型输入上实现次线性的平均性能。
Clinical relevance
字符串匹配是日常工具和基础设施的基础：文本编辑器和命令行工具中的搜索、内容过滤和入侵检测签名扫描、抄袭检测以及生物序列中基序的定位。多模式匹配通过一次处理多个模式的字典来扩展这些应用。
History
Knuth-Morris-Pratt算法（1977年发表，但更早开发）提供了第一个广为人知的线性时间精确匹配器，而Boyer和Moore（1977年）同年引入了次线性平均情况匹配。Rabin和Karp的哈希方法以及Aho-Corasick多模式自动机（1975年）进一步拓宽了该领域。
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Michael Rabin
- Richard Karp
Related topics
Seminal works
- knuth1977
- boyer1977
- cormen2009
Frequently asked questions
- 哪种精确字符串匹配算法最快？
- 这取决于输入。Knuth-Morris-Pratt保证线性最坏情况时间；Boyer-Moore在实际应用中对自然文本通常最快，因为它会跳过字符并平均以次线性运行；Rabin-Karp在搜索多个模式或进行指纹比较时表现出色。没有一个单一的普遍赢家。
- Rabin-Karp如何避免在每个位置比较每个字符？
- 它使用滚动哈希对模式和每个相同长度的文本窗口进行哈希处理，当窗口滑动时，滚动哈希会在常数时间内更新。只有当哈希值匹配时，它才会验证实际字符，因此大多数不匹配的位置都会通过一次廉价的比较被拒绝。