本文首发于个人博客clloz.com 字符串的匹配是编写程序的时候经常遇到的一个问题，也是计算机处理的基础问题之一。最简单的方法是循环字符串，一位一位地进行匹配，也可以使用正则表达式。今天本文讨论用状态机的模型如何理解和解决字符串匹配的问题。 其实我们在编程的过程中其实一直和状态打交道，比如 if/else， switch/case 等，有时候当我们面对一些比较复杂的问题的时候如果能够用有限状态机来描述，那么问题的逻辑可能更清晰。代码结构的可读性也更强。 比如字符串的匹配问题，当我们想要知道某个字符串中是否包含另一个字符串时，状态机就能够帮我们解决问题。比如我们要寻找一个字符串中是否有 abcdef 这串字符，如果使用状态机模型，我们可以这样实现： 用上面的方式我们可以对任意 pattern 进行字符串的匹配。但有个问题是当匹配失败的时候我们是将 i 前进一位，然后对 pattern 从头进行匹配，对一些有重复部分的 pattern 显然是没有效率的。比如 abcabx，当我们匹配到 abcabc 的时候我们没必要从 bcabc 从头匹配，只需匹配第二个 abc 后面是不是 abx 就可以了。而如果使用状态机模型，则可以利用状态的跳转来实现这样的目的。 用状态机模型的方式实现，代码结构也很清晰，每一个状态直接是没有关系的，我们可以通过控制状态的跳转来控制流程，提高匹配的效率。但是这样的实现方式显然也不好，每次出现一个新的 pattern 我们都要重新写代码，并没有将状态机的逻辑完全抽象出来。 KMP 算法的主要思想是提前判断如何重新开始查找，而这种判断只取决于模式字符串本身。-- 《算法4》 在谷歌上搜索 DFM 的中文结果很少，大部分的 KMP 算法的文章都是讲解 PMT 中的 next 数组的含义，通过状态机来讲解这个算法的非常少，而且质量也不是很高。大部分的 DFM 文章都来源于 《算法》第四版 中的 5.3 章节 Substring Search