KMP —— 字符串分析算法





同学们好，我是来自 《技术银河》的 💎 三钻 。



大家可能觉得 KMP 这个算法的名字很特别、很怪，因为 KMP 它并不是三个英文单词的开头，而是三个计算机科学家的名字。发明这个算法的三位计算机科学家分别为：Knuth、Morris、Pratt。第一个是大家都非常熟悉的 Donald Ervin Knuth (高德纳)，他是《计算机设计艺术》的作者，也是编程界非常有名的一位老专家。然后 M 和 P 也都是当时比较著名的计算机专家，而 KMP 匹配算法就是他们三个一起研究出来的 。



什么是 KMP 算法？



快速的从一个主串中找出一个你想要的子串 —— 这里面的主串就是 source 串，而要寻找的 子串 就是 pattern 串 也叫 模式串。



如果我们先不考虑 KMP 算法，我们用一个最朴素的算法，在算法里面经常用到的 Brute-Force(BF) ，这个在历史上也是有一个算法的名称的，就是我们的 "暴力解"。



那么我们怎么使用暴力破解来匹配我们的字符串呢？这里我们需要在一串字符的开始，逐个去与我们的模式串中的字符比对，如果我们能找到一段连续的字符与我们整个模式串中的字符完全匹配的，那么我们可以认为，这串字符中存在与我们模式串的字符一致的字符。这种算法的时间复杂度就是 m 乘以 n的。m 的长度就是原串的长度，而 n 就是模式串的长度。



这种非常高时间复杂度的算法，对我们程序的性能肯定是有严重影响的。所以我们的计算机科学家经过一定的研究发现，通过一些算法的技巧，我们是可以把时间复杂度降到 O(m + n) 。这个就是三个科学家发明的 KMP 的算法。



接下来我们一起来看一下，KMP 匹配算法到底是怎么做的。



KMP 算法匹配过程



我们先来一个简单的例子，假设现在我们有两串字符：



• 主串 (source)：ABABABABABAAABABAA

• 模式串 (pattern)：AAAB



KMP 算法最终的目的就是在我们主串中，找到与我们模式串匹配的子串。看看以下动态效果：





里面红色部分的就是我们的 主串，而我们的蓝色部分就是我们的 模式串。我们快速的在主串中找到了 AAAB 这个子串，而它是与我们的模式串完全匹配的。这里最重要的点就是 "快速"，KMP 算法就是为了可以快速找到我们在主串中的子串。



我们先来了解一下 "不快" 的方式是怎么做的，其实暴力破解法，一般都是比较直观的，也是比较容易可以想到的。



确实不是很难想到，我们暴力破解无非就是让主串和模式串中的所有字母逐个对比和匹配。如果遇到不匹配的，就让模式串顺延整体回到开头字母的下一个的位置，重新开始逐个匹配。以此类推，最后要不我们找到了能匹配上的子串，要不就走到了尽头代表主串中没有可以匹配上模式串的字符串。



好，我们来看看效果图：





这种算法确实很直观对吧？这里我们要注意一个点，就是在第一轮匹配的过程中，当我们遇到不匹配的字符的时候，我们的指针 i 和 j 都会挪动到主串的第二个位置。这个动作我们就叫做 比较指针回溯，那么"回溯" 就是导致这个简单的算法效率比较低的主要原因。



那么我们应该怎么做才能达到我们所说的 "快" 速查找呢？





毋庸置疑，肯定是使用我们的 KMP 算法。KMP 算法可以做到仅仅后移模式串，比较指针不回溯！听起来是不是很牛？那么我们来看看是怎么做到的。



我们回到刚刚发现某一个字符不匹配的状态：





这里我们模式串是在 A 的位置，而我们的主串是在 B 的位置，很明显这里是不匹配的。如果我们细心观察一下前面的 5 个字母中，我们会发现两个重要的现象：



1. 主串和模式串的这一段字符是匹配的。两个都是 ABBAB

2. 模式串左右两端有两个子串 AB 是完全一致的，这两个字符串我们称之为模式串的 公共前后缀





根据这两点，我们就可以使用 KMP 算法中的技巧了，这个也是 KMP 算法的核心，只要理解了它整个算法我们就理解了。我们直接把模式串前缀 AB 的位置直接移动到，模式串后缀所在的位置。







这样一移动我们就可以保证我们当前指针匹配的字符前面的字符串是上下匹配的。也就是说，我们这种移动的方式，可以确保我们 复用 部分的字符是匹配的。在我们例子里面，移动后我们前面的 AB 在主串和模式串中是匹配的。那么为什么会有这样的现象呢？其实就是因为我们的公共前后缀是匹配的，移动后还是可以匹配的。



那么严谨的同学就会有疑问了，我们这么一下子把模式串移到这个位置，那么我们会不会错过了一些其他匹配的情况呢？我可以很负责任的说，移动前和移动后之间的两个位置中，是没有任何可匹配成功的情况。





保持质疑的态度，是一个程序员的基本素养。那么我们来逐个走一篇看看吧。





通过上面的效果图，我们可以看到，从一开始一直移动过来，在到达我们模式串公共后缀的位置之前都是没有能匹配上的。这样也证明了我们上面所说的结果。



上面讲的是一种特殊的情况，那么我们来看看一般情况下是怎么样的。在我们特殊例子中发现了一个特点，在匹配的过程中当我们到达了匹配失败的字符的位置时，模式串的这个位置之前的所有字符都是与主串能匹配的。然后我们是在这段能匹配的字符串里面找 公共前后缀的，也就说我们其实只需要分析 模式串就可以了，因为我们分析的这段字符串是完全与主串一致的。



我们来举一个更通用的例子，比如我们现在有一串字符AB ... ... ABX ... ... ， 这里面 ... 代表着多个任意字符，而 X 代表的就是跟随在 AB 这个公共后缀的字符。X 也能理解为模式串和主串第一个匹配失败的位置。



这个时候我们只需要把 公共前缀 移到 公共后缀所在的位置，就可以继续往后匹配了，这个就是我们刚刚例子里面所讲到的，那么我们也证明了前缀和后缀之间是不会有可以匹配上的情况的。那么如果有，证明我们选择的 公共前后缀 不是最长的公共前后缀。



什么意思呢？就是在匹配失败的位置前面的字符当中，还有更长的前后缀。这里我们就引出了一个 最长公共前后缀 的概念了。



最长公共前后缀就是 —— 当我们分析的字符串中有多个公共前后缀时，我们要取最长的公共前后缀。



到这里 KMP 算法的概念我们就讲完了，接下来我们一起把上面的例子的匹配过程走完。我们就来看一段动画了解一下剩余的匹配过程吧 ~





上面的动画中，我们从第二次匹配的位置开始：



• 因为根据上面的逻辑我们已经把公共前缀 AB 移动到了后缀的位置，所以我们就可以继续逐个字符继续匹配

• 匹配到主串的 B 和模式串的 A 的时候，就发现匹配又失败了

• 这个时候我们去看这个模式串 A 前面已经匹配过的字符 ABBABA，这串字符中只有前后缀 A

• 所以最后我们让模式串从前缀 A 移动到后缀 A 的位置

• 这个时候我们发现我们的模式串长度已经超出了主串的长度，所以这里就说明主串中没有可以匹配这个模式串的子串。



显然这种匹配方法，要比我们的 "暴力解" 的方法的比较次数要少的多，自然我们的算法的效率就会高的多。



接下来我们再看一个例子：



• 主串：ABABABAABABAAABABAA

• 模式串：ABABAAABABAA



首先我们把两个字符串在左边头部对齐，然后我们开始逐个比较主串和模式串中的字母。





到了第六个字母的时候，我们发现不匹配的情况。这个时候我们就开始分析前面匹配过的字符串 ABABA。这里我们需要找到最长的 公共前后缀，找最长前后缀的最佳方法就是从两个末端往内延伸。





在我们上面的这个动画中，我们可以看到我们是怎么寻找最长前后缀的。在这个过程中我们找到了 3 对前后缀：



1. A 和 A

2. ABA 和 ABA

3. ABABA 和 ABABA



这三对前后缀都是完全匹配的，但是第三对是一个无效的前后缀，因为它的长度与我们这串字符的长度是一样的。那么就意味着我们完全不需要移动，就可以从前缀挪动到后缀的位置。这样的话对我们进入下一个匹配没有任何意义。所以只有第一和第二对前后缀是有效的。



通过上面的例子中，我们就可以给寻找公共前后缀加上一个约束条件：我们需要找最长的，并且长度要小于错误位置左端子串长度的公共前后缀。



因为我们需要的是 最长公共前后缀，所以第二组的 ABA 是最适合的。



找到了最长公共前后缀之后，我们就可以把模式串的位置从前缀的位置挪动到后缀所在的位置，然后继续往后匹配字符。





逐个扫描后我们在模式串第 7 个字母又发现了不匹配，这个位置的右边的字符串就是 ABABAA。通过 "上帝视角"，我们一看就能看到这个子串里面只有一对公共前后缀，那就是 A 和 A。





与之前的做法一样，首先把公共前缀的位置挪动到公共后缀的位置，然后继续往后匹配。匹配到最后我们会发现我们在主串中找到一个子串是与模式串完全一致的。这个就得出一个结果，我们的主串中是有我们需要的字符串的（也就是含有我们的模式串的）。



一般我们的字符串都是存在一个字符数组中，而数组在内存中是不可能移动的。所以刚才我们演示的例子都是形象化的过程，我们还需要转化为计算机方便处理的方式。



KMP next 数组



既然我们知道在实际代码中，我们是无法移动数组位置的，那么我们就需要把这个概念转化成代码可以执行的逻辑。



首先我们要理解一个概念，在我们上边的算法匹配过程中，我们知道一直在移动的都是我们的 模式串而我们的主串都是没有任何变动的。所以在 KMP 算法的匹配中，最关键的运算和变化都是在我们的 模式串 之中。



换句话说我们只需要研究模式串，并且把它的相关信息挖掘出来，然后用它就可以跟任何字符串做匹配了。



我们先用一个例子来了解一下我们需要怎么研究一个模式串，并且把它的信息挖掘出来的。



这里我们就用我们之前例子中的 ABABAAABABAA。



首先我们给这个字符串加上下标，方便我们分析：





注意： 这里我们是从下标 0 开始储存的，而很多学校教 KMP 算法的时候，习惯从下标 1 开始储存，但是在代码中，大多数据结构都是从下标 0 开始的，如果我们用了从 1 开始，在写代码的时候就会容易混乱。（个人觉得这也是让本来比较简单的 KMP 算法，变得很难理解的一个原因，有一些教程是从 0，有一些教程是从 1，然后在写代码的时候数组又是从下标 0 开始的。最后搞得我们脑壳疼，掉头发。）



不过就算我们要从下标 1 开始，那我们的匹配串和模式串都要从下标 1 开始，要不我们的 next 数组就是错乱的。**这里为了大家更好理解，而且更接近代码中的原本的数据结构，我们就统一都从下标 0开始。 **



好，那么我们开始分析这个模式串吧。



首先我们假设这个模式串是可以与任何一个主串用 KMP 算法匹配的。那么这个模式串中的每一个字符的位置都有可能发生不匹配的。



但是我们重点要看的是，任何一个位置发生不匹配时，前面那一串字符的公共前后缀长度，从而我们可以获得我们需要回移动模式串的位置。



下标 0 位置



首先模式串的下标 0 的位置，我们是不需要去计算 next 数值的，因为这个位置的字符长度为 1，是无法获得一个最长公共前后缀的，因为 最长公共前后缀的长度必须小于子串自身的长度



所以第一位字符的 next 数值必定是 0。



下标 1 位置



接下来我们往后看，如果是模式串下标 1 这个位置后面的字符发生匹配失败。





• 下标 0 到当前下标的字符是 ab

• 很明显这里是没有公共前后缀的

• 也就是说最长公共前后缀是 0



所以下标 1 的 Next 数值就是 0。



下标 2 位置



接下来我们看看下标 2 位置后面发生匹配失败时的情况。





• 下标 0 到当前下标的字符是 aba

• 这里我们就发现 a 是这个段字符的公共前后缀

• 而这个前后缀的长度是 1



所以下标 2 的 Next 数值就是 1。



下标 3 位置





• 下标 0 到当前下标的字符是 abab

• 这里的公共前后缀就是 ab

• 它的长度就是 2



所以下标 3 的 Next 数值就是 2。



下标 4 位置





• 下标 0 到当前下标的字符是 ababa

• 公共前后缀是 aba

• 它的长度是 3



所以下标 4 的 Next 数值就是 3。



下标 5 位置





• 下标 0 到当前下标的字符是 ababaa

• 公共前后缀是 a

• 它的长度是 1



所以下标 5 的 Next 数值就是 1。



N 位匹配规则



这里我们分析了 5 个下标的 Next 数值，我们显然可以发现一个规律。每一个位置的 Next 数值其实就是，字符串开头到当前位置的字符中的公共前后缀长度。



所以我们把剩余的 Next 数值都写下来看看。





这个就是我们经常在 KMP 算法中听到的 Next 数组 了。



其实很多地方又称这个为 prefix 前缀数组或者 PMT 数组。因为它对应的值，代表的是前字符串中的公共前后缀长度。但是 Next 数组在代码中需 要起到的作用就是 “挪动前缀到后缀所在的位置”。



要做到这个，我们就需要知道在每一个位置，我们前缀最后一个字符的下标位置。很奇妙的是，当前我们的 Next 数组中的每一个数组的前面一个就是我们前缀最后一个字符的位置的下标值。



所以我们只需要把现在的 Next 数组的所有数值整体往右挪动一位即可获得我们真正想要的 Next 数组。



有了这个 Next 数组 我们就可以根据这个数组所提供的信息，在我们模式串任意一个位置发生不匹配时就能找到下一个匹配的位置。



然后我们发现下标 0 的位置就空了，没有数值了。所以我们一般都会给下标 0 位置赋予 -1。



最后我们就会得到这样的数据：





代码实例



接下来我们一起来看看 KMP 的代码应该怎么写。首先 KMP 它肯定是一个 function 并且会接收两个参数，一个是 source 一个是 pattern，分别代表的是 主串 和 模式串。



然后我们的处理会分成两个部分，第一部分我们就是计算 Next 数组，而第二部分才是匹配。



计算 Next 数组



根据我们上面的 KMP 算法的推理逻辑，要算出 Next 数组来做匹配，我们首先就要找到每一个位置的前面字符的最长公共前后缀。而这个数据就是 prefix 前缀数组。



在寻找前后缀的时候，如果我们用 “上帝视角：我们聪明的大脑” 去分析的话，我们是比较容易可以看出一段字符中最长的公共前后缀的。但是对计算机来说，就需要笨拙一点的方法，挨个去比对，而且要写成代码，真的不是那么容易。那怎么办呢？



就像我们解答算法题一样，遇到一个复杂的问题的时候，就试着在复杂的问题里面找简单的规律。从而就能让我们对这个题目做到降纬打击的效果，也就是 “复杂的问题简单化” 的效果。



我们就用上面理论里面讲到的例子 ababaaababaa，首先我们把它每一个匹配字符前面的那一段字符拆出来，并且列出它的公共前后缀，然后找找这里面有没有什么规律：



• ab ：0

• aba：1

• ab ab：2

• ababa：3 (aba, aba)

• ababaa：1

• ababaaa：1

• ababaaab：2

• ababaaaba：3

• ababaaabab：4

• ababaaababa：5



在这里，我们可以找到什么规律呢？其实有的，我们拿 aba 和 abab 这两段字符串来看看。首先我们知道 aba 的公共前后缀是 a，公共前后缀长度是 1。假设我们想让它的最长公共前后缀长度变成 2 的话，我们只要在 aba 的后面加一个 b 就可以了。



所以换一种思维方式，是不是在 aba 的基础上，我们只需要判断它接下来的字符是不是 b 就知道下一段的字符最长公共前后缀的长度呢？



如果 aba 接下来的字符是 b ，下一段字符的公共前后缀必然就是当前最长公共前后缀 + 1，也就是 1+1=2。好，我们来确认这个规则是不是对的！



我们拿 ababaaa 这一段来测试一下，ababaaa 它的最长公共前后缀就是 a， 长度为 1，它前缀最后一个字符的后面，是一个 b。根据我们刚刚的逻辑，如果 ababaaa 的下一个字符是 b 的话，那么最长公共前后缀就可以变成 ab，长度为 2。



果不其然，下一个字符就是 b，而且真的是长度为 2。所以现在的字符是 ababaaab，公共前后缀是 ab，长度为 2。完美，我们找到第一个规律了！



我们来把这个规律总结一下，我们要用公共“前缀”的下一个字符，与我们公共“后缀”的下一个字符做比对，如果它们是一样的，那么我们下一段字符的最长公共前后缀就是 当前最长公共前后缀 + 1。



整个逻辑就如下面的动画一样：





这个动画里面的 j 指向的就是我们公共前缀的末尾字符，而 i 指向的就是我们公共后缀的末尾字符。



细心的同学应该会注意到，其实刚刚说的 当前最长公共前后缀长度 + 1，如果换成是与 j 所在位置的话，也可以理解为 j 所在下标 + 1。我们会发现这个规则也是相同的。（为什么这里又提到这一点呢？因为这个规则更利于我们写成代码。）



那么如果下一个字符是不匹配的呢？好家伙，这个是一个好问题！没关系，我们的例子中也有这样的情况，我们把它们拿出来分析一下，相信我们强大的大脑总能看出一些蛛丝马迹！



那么我们就把 ababa 和 ababaa 单独拿出来看一下。首先 ababa 有一个公共前后缀为 aba，长度为 3，那么如果 ababa 下一个字符出现的是 b，我们就能有一个长度为 4 的公共前后缀了。可惜事实并不会那么容易放过我们，下一个字符是 a。所以这里就出现与我们刚刚讲的场景恰好相反的情况。



"------------ ～ 2 个小时之后 ～ -------------"



怎么办呢？找不到规律呀！！





大家不要误会，我不是很苦恼，只是头皮发麻，所以需要整理一下头发，这也不是程序员经常掉头发的原因，请不要多想哦～



嗯哼～ 回归正题，既然想不到办法了，那么我们就把整个模式串每一个位置对应的最长公共前后缀列成表格，说不定我们就能看破天机了！





上面的表格中，我们标记了两段字符串中的最后一个字母的位置。同时我们也标记了当前 j 和 i 的位置。这里我们可以看到：



• ababa 的公共前后缀是 aba，那么前缀最后一个字符在下标 2 的位置

• ababaa 的公共前后缀是 a, 那么前缀最后一个字符是在下标 0 的位置



同学们，有没有发现什么？其实我们 ababaa 与 ababa 的区别就是这个下标，也就是说如果我们的 j 回溯到下标 0 的位置，我们 j 和 i 指向的字符就是一致了。然后如果 j 回溯到了 0，那么我们又可以使用刚刚分析出来的规则，j 的下标 + 1 = 下一串字符的公共前后缀的长度。



所以这里我们 j 指针回溯（回退）后就是在 0 下标的位置，而下一段字符串的最长公共前后缀就是 0 + 1 = 1。哇～出来啦！这就对了！



这里我们只知道我们 j 是需要回溯（回退）到更前面的下标，但是毕竟我们要把这个逻辑写成代码，那么必须就要有 “规律可寻” 才行。我们再回去看看上面的表格，我们发现 j 指向我们 prefix（前后缀） 的值是 2，那么我们是不是可以用当前 j 下标的 prefix 值替换当前 j 的位置呢？这样我们就可以让 j 回溯到更前面的位置了。



首先我们要知道，我们的 prefix 表中的值，代表的是从头到当前位置的字符串中，所拥有的最长公共前后缀的长度。当前我们 j 所在位置指向的 prefix 值是 2，对应的公共前后缀是 ab，如果我们用这个值去挪动 j 的位置，那么 j 就会指向第三位字符 a，也就是 aba 中的第二个 a 这个位置。



根据我们刚刚整理出来的第一个规则，我们用当前 “公共前后缀” 后面的一个字符与 i 指向的值做匹配。那么现在如果 j 挪动到下标 2 的位置的话，我们来看看它前面的字符是什么？





我们可以看到，j 前面的字符串是 ab。很显然 ab 并不是我们现在 ababaa 这段字符中的公共前后缀。所以这样挪动 j 的位置是不妥的。所以我们还需要换一种策略。



我们目标很简单，就是让 j 回溯到正确的位置，如果当前对应的 prefix 值不行，那么我们拿 j-1 的 prefix 值呢？



j-1 的值，其实就是上面表格中 j 现在对应的 prefix 的值，也就是 1。





这时候我们发现这个 j 的位置对应的字符串公共前缀是对的了。说明我们这种 j 的回溯方法是对的，但是我们又发现 j 位置对应的字符与 i 现在对应的字符不对等。



既然 j 回溯的策略是对的，我们这个时候我们用同样的方式再次让 j 回溯，往前挪动它的位置。这个时候 j-1 的位置就是下标为 0 的位置了。



这个时候，j 指向的字符与 i 指向的字符就一致了。用我们之前的规则，这个时候 i 所在位置前面的字符串的最长公共前后缀就是 0 + 1 = 1。



我们发现我们获得的值就对了。所以有了这规律，我们就可以算出 prefix 表的数据，也就是每一个位置前面的字符拥有的公共前后缀长度。然后我们就可以通过这个 prefix 表获得我们的 next 数组。



我们来总结以下这两条规则：



• i 从 1 下标开始，j 从 0 下标开始，依次匹配彼此位置对应的字符。如果相同，证明 i 当前位置前面的字符拥有一个公共前后缀长度为 j 下标值 + 1

• 如果 i 和 j 对应的字符不匹配，那么 j 就会回溯到更前面的位置找寻一个匹配的字符，回溯的规则为 prefix[j-1]。



这里需要特别注意的是，如果我们的 j 已经回溯到下标为 0 的时候，还是没有找到公共前后缀，那我们就要停止 j 继续回溯了，并且也证明这段字符串没有公共前后缀。



讲了那么多，理论是整理清楚了，接下来看看代码我们应该怎么去实现。



根据上面的理论分析，我们首先需要计算出 prefix 前缀数组，然后在 prefix 数组的所有值往右挪动一位即可获得我们的 Next 数组。



在生成 Next 数组这里我们会用一个 next 变量来储存数据。根据我们上面分析出来的 Next 数组，它的长度肯定是和我们模式串的长度一致的，所以我们创建 Array 的时候就直接给 table 填好数据。这里我们都填入 0 即可。



function kmp (source, pattern) {
  // 计算 Next 数组
  let next = new Array(pattern.length).fill(0);
    
  // 寻找模式串中的公共前后缀
  let i = 1,
    j = 0;
}



按照我们之前讲的，下标 0 号位，我们是不需要分析它的 next 值的，所以我们的 i 可以直接从 1 下标开始。这里 i 默认值是 1， j 默认值是 0。



接下来我们就可以开始循环我们的模式串。这里我们使用一个小技巧，在上面讲理论的时候，我们是先计算出 prefix 前缀数据，然后通过把所有的值整体往右挪动一位，获得我们的 next 数组。



但是其实在我们循环的过程中，就可以做到这一点。每次我们比对 i 和 j 对应的值的时候，如果我们发现匹配成功，我们就把 对应的 prefix 值，放到当前下标下一个位的位置。也就是 next[j+1]。这样我们就一定把所有 prefix 值往右挪动了一位。也就不需要在后面再统一挪动一次了。



好，有了这个技巧，我们就可以快乐去编写 Next 数组的生成代码啦～



这里我们就运用刚刚分析出来的两条规则来处理两种情况。第一种就是 i 对应的字符与 j 对应的字符相同，这个时候我们就知道 prefix 值就是 j + 1。



我们知道了 prefix 值，根据上面所说的技巧，我们需要把这个值放入 next[j+1] 的位置。



不过，因为我们 i 和 j 是匹配的，所以我们同时是需要把 j 和 i 挪动到下一个下标的位置。因为 j 挪动了一位，其实就等于 j 自身已经 +1 了。那么我们赋值给 next 的时候就可以直接用 next[i] = j，这里 i 也一样不需要再 +1 了，因为 i 挪动到下一个下标的时候已经自身也 +1 了。



然后就是第二种情况，当 i 和 j 对应的字符不匹配的时候，我们就要让 j 进行回溯。因为我们已经把 prefix 数组的值往右挪动了一位，所以我们直接用 j = next[j] 即可，就不要获取 next[j-1] 的值了。



最后，我们前面讲过，如果 j 已经回溯到下标 0 还是没有发现有公共前后缀的情况。这个时候我们就不能让 j 继续回溯了，所以我们需要控制这种边界的情况，只有 j > 0 的时候才会继续回溯。如果到达了下标 0 还是没有发现公共前后缀， 那就可以让 i 往前挪动一位了。



注意：我们一开始就给 next 数组里面所有的值都赋予 0，所以遇到 i 和 j 不匹配的时并且 j 已经在下标 0了，这个时候我们不需要给 next 数值赋值 0 了，因为它本来就已经是 0 了。



在理论部分我们讲到，Next 数组的下标 0 在挪动后是空值，所以需要补一个 -1，为了保持一直，最后我们加上这个逻辑 next[0] = -1。



这里还有一个点需要我们注意的，就是我们的循环截止的条件是 pattern.length - 1，而不是 pattern.length，这是因为我们已经把 prefix 数组的值都往后挪动了一位，所在如果我们使用 pattern.length 条件的话，如果我们一共有 11 个字母，在循环到 i = 11 的时候，我们一样调用了 next[11 + 1] = j，自然这里就多出了一个数值。而这个我们是需要的。所以这里我们截止条件改为 pattern.length - 1 即可。



这个逻辑的动态效果如下：





function kmp(source, pattern) {
  // 计算 Next 数组
  let next = new Array(pattern.length).fill(0);
  // 寻找模式窜中的公共前后缀
  let i = 1,
    j = 0;
  while (i < pattern.length - 1) {
    if (pattern[i] === pattern[j]) {
      ++j, ++i;
      next[i] = j;
    } else {
      if (j > 0) {
        j = next[j];
      } else {
        ++i;
      }
    }
  }
    
  next[0] = -1;
  console.log(next);
}
kmp('', 'ababaaababaa');



这里我们调用一下 kmp 函数来试试，最终的 next 数组是不是对的。





完美，这样我们就达到我们预期的 next 数组了。接下来就是去实现我们的匹配逻辑了。



匹配



其实匹配的逻辑是和我们计算 Next 数组的逻辑是基本相似的。最大的区别就是现在不是模式串于自己的字符对比，而是于原串的字符做对比。



在这个匹配的循环里面，我们又需要用到 i 和 j，这样其实我们作用域就冲突了。所以这里我们用到一个小技巧，在我们用 {} 包着我们计算 Next 数组代码，这样它里面的 i 和 j 就只限于这部分的代码。然后我们匹配的代码也是一样，用 {} 包着即可。



这个匹配逻辑我们 i 和 j 就都是需要从下标 0 开始了。



然后我们的循环会一直循环直到 i 到达我们原串的长度。



循环中的逻辑如下：



• 首先我们判断匹配成功的情况，模式串 中的 j 指向的字符与 原串 中 i 指向的字符相同时，i 和 j 就都可以往右挪动一位，往后继续匹配了。

• 根据我们分析 KMP 的回溯方式，我们就需要把前面一段字符的公共前缀挪动到公共后缀的位置，所以我们就可以使用计算好的 next 数组的值： j = next[j] 进行移动。

• 但是还有一种情况，就是当前的 j 是在下标 0 的位置，这样的话，其实根本就不可能有公共前后缀的。这种情况我们就可以直接找原串中的下一个字符与我们模式串的下标 0 的字符进行匹配了，所以这里就是 ++i 即可。

• 所有我们判断一下，当前 j 的位置是否一定到达模式串的最后一位了，如果是，证明我们已经匹配成功。

• 如果走完整个原串的所有字符，我们模式串还没有全部被匹配到，这就证明我们原串中没有一个子串与我们模式串相同，即时匹配失败。



按照上面的逻辑，我们的代码就是这样的：



function kmp(source, pattern) {
  // 计算 Next 数组
  let next = new Array(pattern.length).fill(0);
  {
    // 寻找模式窜中的公共前后缀
    let i = 1,
      j = 0;
    while (i < pattern.length - 1) {
      if (pattern[i] === pattern[j]) {
        ++j, ++i;
        next[i] = j;
      } else {
        if (j > 0) {
          j = next[j];
        } else {
          ++i;
        }
      }
    }
    next[0] = -1;
  }
  // 匹配
  {
    let i = 0,
      j = 0;
    while (i < source.length) {
      if (pattern[j] === source[i]) {
        ++j, ++i;
      } else {
        if (j > 0) {
          j = next[j];
        } else {
          ++i;
        }
      }
      if (j === pattern.length) return true;
    }
    return false;
  }
}
console.log(kmp('ABABABAABABAAABABAA', 'ABABAAABABAA'));
console.log(kmp('helbbblo', 'll'));



最后我们执行了这个不同的字符匹配例子。如果我们的 KMP 算法的代码是正确的，第一个字符匹配应该是成功的，而第二个应该会失败。我们来执行一下看看，是否正确。





显然这里是正确的。这样我们就完成了 KMP 算法的代码实现了。



希望这篇文章可以让大家更好的理解 KMP 算法，说实话，因为市面上有很多教程，很多文章讲解这个算法的。但是我看了很多，基本讲法都各有不同，prefix，PMT，next 这些概念也是各有各的说法。经过我一番研究，其实实际上最后的实现都是一样的，其实就是按个更好理解而已。对我而言，使用 prefix 和 next 这两种概念是最好理解的。



这篇文章是我所有文章中花时间最长的一篇，总共重写了 3 遍，因为 KMP 不同的文章的差异，让我刚开始整理的时候走入了很多误区，导致对 KMP 的知识越看就越混乱。最后看了很多视屏和文章，然后一一研究后才真的弄懂了它们。如果这篇文章让你们对 KMP 有了更清晰的认知，那就给我点赞三连吧～ 谢谢～





博主开始在B站直播学习，欢迎过来《直播间》一起学习。



我们在这里互相监督，互相鼓励，互相努力走上人生学习之路，让学习改变我们生活！



学习的路上，很枯燥，很寂寞，但是希望这样可以给我们彼此带来多一点陪伴，多一点鼓励。我们一起加油吧！ (๑ •̀ㅂ•́)و





我是来自微信公众号《技术银河》的三钻，一位正在重塑知识的技术人。下期再见。