第 11 章 字符串匹配——1969年，一位程序员发现计算机竟然不会利用自己的记忆标记本章已读大字阅读打印本章回到上次阅读位置交互模块加载失败。正文仍可阅读，请刷新重试。正在加载交互实验…第一季 · 人类如何驯服数据来源历史主线：1969—1977年 · CDC 6400、有限自动机、KMP、Aho–Corasick、Boyer–Moore1969年夏天，美国。一位年轻的计算机科学家正在为 CDC 6400 大型计算机编写文本编辑器。他的任务非常普通：在一段文字中，找出某个指定的字符串。例如，从一份长达几十万字符的文件中寻找：ALGORITHM按照我们今天的经验，这似乎是一个再简单不过的功能。可是，当时的计算机存在一个令人头疼的问题。文本可能存储在外部文件中，程序通过缓冲区依次读取。如果一次匹配到一半，突然发现不匹配，传统算法可能需要把文本读取位置退回去，再从下一个起点重新开始。这种反复回退，会让缓冲区管理变得十分复杂。于是，这位年轻人开始思考：如果已经比较过的字符包含足够的信息，为什么计算机还要回到过去，重新检查它们？他想出了一种新方法。后来，他的代码被其他程序员修改，却因为过于复杂而变得难以维护。更戏剧性的是：大约一年之后，另外两位研究人员通过完全不同的理论途径，竟然得出了与他几乎相同的算法。这三个人是：James H. Morris Jr.、Donald Knuth、Vaughan Pratt。而他们共同留下的，就是著名的：KMP 字符串匹配算法。这一次，我们有一份特别珍贵的历史证据：三位研究者在1977年正式发表的论文中，亲自详细写下了算法被发现的过程。[SIAM Journal on Computing][cs.brown.edu]第一幕：为什么查找几个字母，会成为计算机的难题？我们先回到1969年的计算机实验室。来源来源来源来源来源来源来源来源一台 CDC 6400 是昂贵而复杂的大型计算设备。它与今天个人电脑最大的不同之一，并不是简单的运算速度。而是输入输出环境。今天，我们打开一个文本文件，操作系统通常会协助管理文件缓存、磁盘读写和内存页面。但在1960年代，程序员需要更直接地面对设备与缓冲区。假设你正在阅读一个很长的文本流。你已经读到了第10,000个字符。现在发现前面的匹配失败了。传统的字符串匹配算法可能告诉你：“请回到第9,994个字符，重新开始。”可是，那个字符可能已经不在当前缓冲区。于是程序需要重新组织缓存，甚至重新读取文件。这不仅影响速度，还增加了程序复杂度。最直接的字符串搜索假设我们要在文本中寻找：ABABAC文本为：ABABABAC最直观的方法叫作朴素匹配（Naive String Matching）。从位置0开始，对比：text复制代码文本：ABABABAC 模式：ABABAC前五个字符的比较结果是：A=B? 不，我们具体按位检查：A 对 A，成功。B 对 B，成功。A 对 A，成功。B 对 B，成功。A 对 A，成功。C 对 B，失败。我们已经正确匹配了五个字符。但只因为第六个字符不同，传统算法便把模式向右移动一位，再从模式开头比较。它往往会再次检查文本中已经读过的位置。接着向右移动，又继续重新检查。我们刚才花费的比较工作，被大量浪费了。问题并不是比较太慢，而是算法没有充分利用先前比较所获得的信息。一个可以亲眼看到的对比实验一：普通搜索如何重复工作Naive Search原始文本ABABABAC当前模式位置：0ABABAC 本轮匹配了 5 个字符，随后发生不匹配。本轮字符比较：6 次重置模式右移一位 →观察最重要的一点：文本中的前几个字符已经参与过比较。但是下一轮，朴素算法又重新比较了它们。在最坏情况下，如果文本长度是 nnn，模式长度是 mmm，传统逐位置匹配需要：O(nm)O(nm)O(nm)时间。如果文本和模式中存在大量重复字符，这种问题会特别明显。那么，1969年的 Morris 究竟发现了什么？第二幕：James Morris——一个太复杂、最终被同事改坏的算法来源James H. Morris Jr.计算机科学家 · KMP 算法共同发明者早年研究程序语言、形式化方法与计算机系统，后来还参与过编程环境和软件系统的研究与开发。1969年夏天，Morris 正在开发 CDC 6400 计算机的文本编辑器。他面临的问题很实际：为了寻找文本中的字符串，编辑器不应该不断后退文件读取位置。于是，他借助有限自动机（Finite Automata）的思想，设计出了一种可以向前扫描文本的匹配程序。其基本机制，与后来发表的 KMP 已经等价。但事情并没有像我们想象的那样顺利。Morris 后来发现，自己的程序逻辑过于复杂，其他维护该系统的程序员并不容易理解。几个月之后，其他人对代码进行了一系列本意是修复问题的修改。结果却破坏了原来的算法。三位作者在1977年论文第7节中，亲自记录了这段经历。[cs.brown.edu]这是软件工程史上一个非常有价值的小故事。一个算法能够运行，并不意味着它容易理解、验证和维护。Morris 已经有了正确的核心思想。但他尚未充分认识到，这套程序竟然拥有线性时间复杂度。他也没有把它整理成今天这种人人都能在算法教材里看到的简洁形式。接下来，第二位主角登场。第三幕：1970年，Knuth 试图验证一个自己不敢相信的数学定理来源Donald Knuth1938年出生 · 算法分析与程序设计理论先驱他不仅是《计算机程序设计艺术》的作者，也在自动机、组合数学、排版系统等领域留下了重要成果。1970年初，Knuth 得知了 Stephen Cook 的一项令人惊讶的理论成果。Cook 研究了某种具有双向读取能力的确定性下推自动机。其结果意味着：一类看起来非常复杂的语言识别问题，可以通过适当的算法在线性时间内解决。Knuth 对此感到疑惑。因为他此前认为，某些与回文相关的字符串识别问题，在常规计算机上可能需要接近平方级别的计算。因此，他决定亲自跟随 Cook 的数学构造，一步一步把理论转换成可执行的算法。这是一条与 Morris 完全不同的研究路线。Morris 从文本编辑器的实际需求出发。Knuth 则从一个自动机复杂度定理出发。经过数小时的推导，Knuth 逐渐发现了其中的机制，并把它提炼成一种利用已匹配前缀信息的字符串算法。他后来表示，这是自己第一次切身体验到：自动机理论能够教会他如何比过去更好地解决一个实际编程问题。[cs.brown.edu]随后，Knuth 把研究结果交给了 Vaughan Pratt。第四幕：Pratt 的改进，让三个研究方向终于汇合来源Vaughan Pratt计算机科学家 · 形式语言、逻辑和算法研究者他也因 Pratt Parser 等程序语言分析技术而被程序员熟知。Pratt 研究 Knuth 的方法之后，对数据结构进行了修改。其中一个重要改进，是让算法的时间界限不依赖字母表的大小。随后，Pratt 把这一算法讲给 Morris。接下来发生了全篇最精彩的历史一幕。Morris 听完之后发现：这不就是自己1969年已经设计过的方法吗？他很高兴地得知，自己当年为解决编辑器缓冲问题设计的程序，原来可以证明拥有 O(n+m)O(n+m)O(n+m) 的时间复杂度。Knuth 则有些懊恼，因为 Morris 在没有依赖 Cook 定理的情况下，已经提前找到了这套方法。不过，三人也认识到，两条不同研究路线都受到了自动机思想的启发。[cs.brown.edu]1970年，Morris 与 Pratt 撰写了一份关于线性字符串匹配算法的技术报告。1974年，三人共同提交正式论文。1977年6月，论文终于发表于 SIAM Journal on Computing：Fast Pattern Matching in Strings。◇1977年 KMP 原始论文Donald E. Knuth、James H. Morris Jr.、Vaughan R. Pratt，SIAM Journal on Computing，第6卷第2期，323—350页。阅读28页原始论文 PDF论文最初提交日期为1974年8月29日，修订于1976年4月，正式发表于1977年6月。[Department of Computer Science]这一段历史特别值得记住。三位研究者不是按照姓名顺序共同坐在一张桌子前，从零开始创造算法。而是：Morris 为解决实际软件问题，独立发现了相关方法。Knuth 从复杂度与自动机理论出发，独立推导出同一方向的算法。Pratt 改进了算法的数据组织，并帮助把研究路线汇合起来。这是一次真正的理论与工程相互促进。而接下来，我们就来亲手发现这套算法的核心。第五幕：KMP 最聪明的地方——它知道什么不需要重新比较我们继续使用：text复制代码文本：ABABABAC 模式：ABABAC假设已经匹配成功：ABABA但接下来的字符不匹配。传统算法想的是：“本轮失败，换一个起点，重新比较。”KMP 想的却是：“既然 ABABA 已经匹配成功，我究竟知道了什么？”仔细观察：已经匹配成功的字符串ABABA前缀：ABA后缀：ABA你发现了吗？字符串 ABABA 的开头三个字符是：ABA结尾三个字符也是：ABA于是 KMP 推断：既然已经匹配的文本结尾是 ABA，而模式开头也是 ABA，那么下次匹配根本不需要从头再验证这三个字符。这些信息已经由此前的比较确定了。所以，KMP 不必把文本指针往回移。它只要调整模式中“已经匹配了多少字符”这个状态。这就是 KMP 的核心秘密。第六幕：LPS 数组——把过去的成功变成未来的捷径在现代 KMP 教学中，我们经常使用一个数组：LPS，Longest Proper Prefix which is also Suffix。中文通常称为：最长相等真前后缀长度数组。其中“真”意味着不能把整个字符串本身同时当作前缀和后缀。例如：ABABA其最长相等真前后缀为：ABA长度为3。所以：LPS[4]=3LPS[4]=3LPS[4]=3下标从0开始。我们把模式 ABABAC 的所有前缀列出来：下标当前前缀最长相等真前后缀LPS0A无01AB无02ABAA13ABABAB24ABABAABA35ABABAC无0因此：LPS=[0,0,1,2,3,0]\boxed{LPS=[0,0,1,2,3,0]}LPS=[0,0,1,2,3,0]注意，论文中的 next 或 failure function 与现代教材中的 LPS，可能采用不同的下标和定义约定。我们这里使用最常见的0起始 LPS 写法，而不是逐字符复刻1977年论文的原始程序。实验二：手动探索前后缀LPS 观察实验前缀函数0A1B2A3B4A5C观察到下标 4LPS = 3当前子串：{cut}相等真前缀ABA相等真后缀ABA拖动滑块，看随着字符串增长，LPS 如何变化。尤其留意最后加入 C 时，原来能够复用的前后缀关系为什么消失。如何计算 LPS？我们可以自己写一个函数：python复制代码def build_lps(pattern): lps = [0] * len(pattern) length = 0 i = 1 while i < len(pattern): if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 elif length > 0: length = lps[length - 1] else: lps[i] = 0 i += 1 return lps最难理解的是：python复制代码length = lps[length - 1]为什么不是简单写：python复制代码length = 0因为当前候选的前后缀匹配失败，不代表更短的候选也必然失败。我们可以利用此前算好的 LPS，找到下一个更短但仍有可能成功的候选长度。而且不需要重新从头比较。这正是整个 KMP 思想的一次自我应用：构造“避免重复比较的表”时，也利用已经计算出来的表避免重复比较。整个 LPS 构造过程的时间复杂度是：O(m)O(m)O(m)其中 mmm 是模式长度。第七幕：让 KMP 在我们眼前运行现在我们有了 LPS。接下来，我们让它搜索：text复制代码Text = ABABABAC Pattern = ABABAC两个指针：i 表示当前文本位置。j 表示已经匹配的模式长度，也是下一次要比较的模式位置。如果相等：python复制代码i += 1 j += 1如果不相等，且 j > 0：python复制代码j = lps[j - 1]注意：这里没有修改 i。这就是为什么 KMP 不需要回退文本指针。KMP 单步调试器观察 i 与 j 为什么不必同时回退第 1/10 步文本字符0A1B2A3B4A5B6A7C模式当前对齐位置ABABAC 文本 i0模式 j0累计比较1文本位置 0 与模式位置 0 相等。从头演示下一步 →你会发现，KMP 并不是跳过比较逻辑。它依然逐字符核对。但当某个匹配失败时，已经匹配的部分告诉我们：某些较短前缀其实已经在当前文本结尾出现。因此，算法只需要改变当前模式状态。完整 Python 实现python复制代码def kmp_search(text, pattern): if not pattern: return 0 lps = build_lps(pattern) i = 0 j = 0 while i < len(text): if text[i] == pattern[j]: i += 1 j += 1 if j == len(pattern): return i - j elif j > 0: j = lps[j - 1] else: i += 1 return -1这段程序返回第一次出现的位置。例如：python复制代码text = "ABABABAC" pattern = "ABABAC" print(kmp_search(text, pattern)) # 2KMP 为什么是线性的？最值得关注的是两个指针的运动方式。文本指针 i 只会增加，不会后退。模式指针 j 虽然可能在失配时减小，但每次成功比较最多使它增加1。因此，整体状态调整次数可以被线性数量限制。预处理 LPS：O(m)O(m)O(m)扫描文本：O(n)O(n)O(n)合起来：O(n+m)\boxed{O(n+m)}O(n+m)空间复杂度：O(m)O(m)O(m)这里的 nnn 是文本长度，mmm 是模式长度。相比最坏 O(nm)O(nm)O(nm) 的朴素匹配，KMP 获得了一个重要保证：即使输入存在大量重复字符，它仍然能够保证线性时间。第八幕：1975年，如果要同时寻找一千个单词呢？故事并没有随着 KMP 的完成而结束。因为软件工程师很快遇到了一个新问题：只寻找一个模式，KMP 非常合适。可是，如果我们需要在一份文本里同时寻找1000个关键词呢？例如：ERRORWARNINGFAILEDTIMEOUT……如果对每个关键词独立运行 KMP，就需要重复扫描同一段文本。1975年，Alfred V. Aho 与 Margaret J. Corasick 在 Communications of the ACM 上发表：Efficient String Matching: An Aid to Bibliographic Search即《高效字符串匹配：辅助文献检索》。他们构造了一种有限状态模式匹配机器，可以在一次文本扫描中寻找多个关键词。论文还记载，这种方法使一个图书馆文献检索程序的速度提高了5到10倍。[Bishtref]这种方法后来被称为：Aho–Corasick 算法，简称 AC 自动机。它结合了：Trie（字典树）：保存多个关键词共享的前缀。Failure Links（失败链接）：匹配失败时跳转到仍可能成功的状态。有限自动机：不断读取输入字符并更新状态。你应该已经发现：AC 自动机和 KMP 使用了高度相似的思想。都是不把已经获得的匹配信息简单丢弃。但 AC 自动机把单个模式的前缀状态，扩展成了多个关键词构成的共享状态结构。第九幕：1977年，Boyer 和 Moore 从相反方向开始比较来源Robert S. Boyer 与 J. Strother Moore他们在1977年发表了另一篇著名论文：A Fast String Searching Algorithm。KMP 在模式内部通常从左到右进行比较，依靠失败函数避免回退文本指针。Boyer–Moore 却提出了另一种很有意思的策略。为什么不从模式的最后一个字符开始比较？假设要寻找：NETWORK而当前文本对应位置的最后一个字符是 X。如果 X 根本没有出现在模式里，那么模式可以直接向右移动较大的距离。不必每次只移动一位。这就是坏字符规则（Bad Character Rule）的基本思想。完整的 Boyer–Moore 还使用好后缀规则（Good Suffix Rule），进一步减少无意义比较。在很多实际文本搜索场景中，它可以跳过大量文本位置，因此平均表现非常出色。但具体性能与字符分布、模式长度、实现方式等因素有关，不能简单说 Boyer–Moore 在任何输入下都比 KMP 快。[bishtref.com][boost.org]三种算法的思想对照算法年份核心思想Aho–Corasick1975多模式共享前缀与失败链接KMP1977正式发表复用已匹配前后缀，不回退文本Boyer–Moore1977从模式右端比较，尽可能大步跳过而这也说明：算法发展并不是一场“谁最终击败谁”的比赛。不同的研究者在不同场景中，找到适合各自问题的解决方案。第十幕：我们今天为什么还需要学习 KMP？你可能会问：Python 已经有：python复制代码text.find(pattern)C++ 也有：cpp复制代码text.find(pattern)为什么还需要自己实现 KMP？因为在实际开发中，我们未必总会直接使用 KMP。现代标准库可能针对不同数据类型、处理器、模式长度采用更适合的搜索实现，语言标准通常也不要求必须使用 KMP。但是，KMP 背后的思想非常值得学习。日志与错误检测如果程序需要从不断到来的日志流里寻找固定关键词，KMP 可以在不回退输入流的前提下维护匹配状态。网络协议分析当数据一块块抵达时，一个模式可能横跨两个缓冲区。KMP 可以保存当前匹配长度，在下一块数据到达时继续处理，而不必重新扫描整个历史文本。DNA 序列DNA 可以表示为由 A、C、G、T 等符号组成的序列。在长序列中寻找短片段，也是字符串匹配问题。不过，真实生物信息学常常还需要处理突变、插入、缺失和近似匹配，这时需要更复杂的算法。编译器与文本处理词法分析器、简单模式检索、协议解析，都可能利用有限状态机与前缀状态的思想。这里更深刻的意义是：KMP 展示了如何将过去的比较结果，压缩成一个很小的状态，并让这个状态指导未来的计算。它与我们之前学习过的动态规划、哈希表、自动机甚至回溯搜索，都有思想上的联系。终章挑战：为什么不能退回到0？假设我们已经匹配成功：ABABA但接下来发生不匹配。你已经知道：已匹配部分开头是 ABA。已匹配部分结尾也是 ABA。那么，在 KMP 中，下一步合理的处理方式是什么？工程师的选择模式状态直接清零，文本回退重新检查保留长度3的前缀匹配状态，继续检查当前文本字符跳过当前字符，直接继续后面的文本认为已有的5个字符足以证明完整模式匹配尾声：三位科学家，让计算机不再重复走过的路1969年，Morris 为了避免文本编辑器反复回退文件读取位置，设计了一套特殊的匹配方法。1970年，Knuth 从自动机理论与复杂度研究中，独立推导出相似的机制。Pratt 改进了算法，并让不同研究路线最终汇合。1977年，三人共同发表了正式论文。这一段历史最大的魅力，不在于算法最后由三个人共同署名。而在于它展示了计算机科学中两种重要力量的交汇：实际工程问题推动算法创新，数学理论则帮助人们理解算法为什么正确、究竟能有多快。Morris 已经拥有可以工作的算法，却未能清楚地看到其线性复杂度。Knuth 与 Pratt 则帮助揭示、简化和分析了这套方法。于是，一种原本为解决文本编辑器缓冲问题而发展出来的技术，逐渐变成了今天数据结构与算法课程中的经典内容。这也把我们整个系列中反复出现的思想再次串联起来：数组教会我们按地址访问。链表教会我们保持灵活连接。哈希表教会我们利用键直接定位。动态规划教会我们复用已经解决的子问题。而 KMP 则告诉我们：一次失败的比较，并不意味着此前的计算没有价值。真正聪明的算法，甚至懂得利用失败留下的信息。第十一章知识总结概念核心思想Naive Matching从每个可能的起点重新比较Prefix / Suffix字符串的前缀和后缀LPS最长相等真前后缀的长度Failure Function失配后应回到哪个有效状态KMP不回退文本，利用前缀信息继续匹配AC Automaton同时匹配多个关键词Boyer–Moore利用失配信息大步跳过文本本章原始资料Knuth、Morris、Pratt（1977）：《Fast Pattern Matching in Strings》期刊档案KMP 完整原始论文 PDF，特别推荐第7节 Historical Remarks，其中详细记载了1969年至1970年算法被独立发现、改进并合流的过程。Aho、Corasick（1975）：《Efficient String Matching》Boyer、Moore（1977）：《A Fast String Searching Algorithm》下一章预告第十二章：压缩算法——1948年，信息究竟能被压缩到多小？1948年，贝尔实验室。一位32岁的数学家发表了一篇论文。他问了一个极为基础，却又改变整个信息时代的问题：信息到底是什么？如果一个字母出现得非常频繁，为什么还要用与其他字母相同长度的编码来表示它？如果某种字符几乎不会出现，是否应该为它分配更长的编码？这位数学家叫作 Claude Shannon，克劳德·香农。他在1948年发表的《通信的数学理论》，为信息熵与数据压缩建立了数学基础。1952年，David Huffman 又提出一种优雅的编码方法。据流传的发明故事，Huffman 当时还是一名学生，正在为完成一项课程作业而苦恼。他最后想出的方案，竟然成为压缩技术史上的经典算法。下一章，我们要研究：为什么出现概率越高的字符，应该使用越短的编码？以及一棵二叉树，如何让文字占用更少的空间。上一章第十章：回溯算法——1848年，一位棋手提出了连高斯都没能完全解开的谜题下一章第十二章：压缩算法——1948年，信息究竟能被压缩到多小？