带你轻松理解KMP算法-js教程-PHP中文网

首页

web前端

js教程

带你轻松理解KMP算法

little bottle

Apr 30, 2019 pm 02:25 PM

jskmp算法

KMP（The Knuth-Morris-Pratt Algorithm）算法用于字符串匹配，从字符串中找出给定的子字符串。但它并不是很好理解和掌握。而理解它概念中的部分匹配表，是理解 KMP 算法的关键。

这里的讨论绕开其背后晦涩难懂的逻辑，着重从其运用上来理解它。

字符串查找

比如从字符串 abcdef 中找出 abcdg 子字符串。

朴素的解法，我们可以这样做，

分别取出第一位进行匹配，如果相同再取出各自的第二位。
如果不同，则将索引后移一位，从总字符串第二位开始，重复步骤一。

这种朴素解法的弊端在于，每次匹配失败，索引只后移一位，有很多冗余操作，效率不高。

在进行第一轮匹配中，即索引为 0 时，我们能够匹配出前四个字符 abcd 是相等的，后面发现想要的 g 与真实的 e 不符，标志着索引为 0 的情况匹配失败，开始查看索引为 1 时，但因为我们在第一轮匹配中，已经知道了总字符串中前四个字符的长相，但还是需要重复地挨个进行匹配。

部分匹配表/Partial Match Table

以长度为 8 的字符串 abababca，为例，其部分匹配表格为：

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif">char:  | a | b | a | b | a | b | c | a |<br>index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | <br>value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |</span>

其中 value 行便是部分匹配表的值。

子集

对于上面示例字符串，假如我们观察第 index 为 2 的位置，那么我们得到了字符串的一个子集 aba，如果我们观察 index 为 7 的位置，那得到的是整个字符串，这点是很显然的。当我们观察的位置不同时，表示我们关注的字符串中的子集不同，因为子字符串发生了变化。

前缀 & 后缀

对于给定的字符串，从末尾开始去掉一个或多个字符，剩下的部分都叫作该字符串的真前缀（Proper prefix），后面简称前缀。这里「真」不是「真·前缀」的意思，联想一下数学里面集合的「真子集」。比如 banana，其前缀有：

b
ba
ban
bana
banan

同理，从首部开始，去掉一个或多个字条，剩下的部分是该字符串的真后缀（Proper suffix）。还是 banana，其后缀有：

anana
nana
ana
na
a

部分匹配值

可以看到，所有前缀和后缀在数量上是对称的，那么我们可以从前缀中找出一个，与后缀进行匹配，先不关心做这个匹配的意义。以最开始的文本 abababca 为例。

假如我们观察 index 为 2 的位置，此时子字符串为 aba，其前后缀分别为：

前缀：a，ab
后缀：ba，a

将前缀依次在后缀中去匹配，这里前后缀列表中能够匹配上的只有 a 这个子字符串，其长度为 1，所以将这个观测结果填入表中记下来，与开始看到的部分匹配表吻合了。

再比如来观察 index 为 3 的位置，此时得到的子字符串为 abab，此时的前后缀为：

前缀：a，ab，aba
后缀：bab，ab，b

此时可观察出其匹配项为 ab，长度为 2，也与上面部分匹配表中的值吻合。

再比如来观察 index 为 5 的位置，此时子字符串为 ababab，前后缀为：

前缀：a，ab，aba，abab，ababa
后缀：babab，abab，bab，ab，b

然后拿前缀中每个元素与后缀中的元素进行匹配，最后找出有两个匹配项，

ab
abab

我们取长的这个 abab，其长度为 4。

所以现在再来看上面的部分匹配表，一是能理解其值是怎么来的，二是能理解其表示的意义，即，所有前缀与后缀的匹配项中长度最长的那一个的长度。

当我们继续，进行到 index 为 6 时，子字符串为 abababc，可以预见，前后缀中找不到匹配。因为所有前缀都不包含 c，而所有后缀都包含 c。所以此时部分匹配值为 0。

再继续就到字符串末尾了，即整个字符串 abababca。也可以预见，因为所有前缀都以 a 开始，并且所有后缀都以 a 结尾，所以此时的部分匹配值最少为 1。继续会发现，因为后面的后缀开始有 c 的加入，使得后缀都包含 ca，而前缀中能够包含 c 的只有 abababc，而该长度 7 与同等长度的后缀 bababca 不匹配。至此就可以得出结论，匹配结果就是 1，没有更长的匹配了。

部分匹配表的使用

利用上面的部分匹配值，我们在进行字符串查找时，不必每次失败后只移动一位，而是可以移动多位，去掉一些冗余的匹配。这里有个公式如下：

If a partial match of length partial_match_length is found and table[partial_match_length] > 1, we may skip ahead partial_match_length - table[partial_match_length - 1] characters.

如果匹配过程中，匹配到了部分值为 partial_match_length，即目前找出前 partial_match_length 个字符是匹配的，将这个长度减一作为部分匹配表格中的 index 代入，查找其对应的 value 即 table[partial_match_length-1]，那么我们可以向前移动的步长为 partial_match_length - table[partial_match_length - 1]。

下面是本文开始时的那个部分匹配表:

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif">char:  | a | b | a | b | a | b | c | a |<br>index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | <br>value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |</span>

假设需要从 bacbababaabcbab 中查找 abababca，根据上面的公式我们来走一遍。

首次匹配发生在总字符串的第二个字符，

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif">bacbababaabcbab |<br> abababca</span>

此时匹配的长度为 1，部分匹配表中索引为 1-1=0 的位置对应的部分匹配值为 0，所以我们可以向前移动的距离是 1-0 1。其实也相当于没有跳跃，就是正常的本次匹配失败，索引后移一位的情况。这里没有节省任何成本。

继续直到再次发生匹配，此时匹配到的情况如下：

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif">bacbababaabcbab    |||||<br>    abababca</span>

现在匹配到的长度是 5，部分匹配表中 5-1=4 对应的部分匹配值为 3，所以我们可以向前移动 5-3=2，此时一下子就可以移动两位了。

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif">    上一次的位置    | 最新移动到的位置    | |bacbababaabcbab<br>    xx|||<br>      abababca</span>

此时匹配到的长度为 3，查找到 table[partial_match_length-1] 即 index 为 2 对应的值为 1，所以可向前移动的距离为

3-1=2。

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif">bacbababaabcbab<br>      xx|<br>        abababca</span>

此时我们需要查找的字符串其长度已经超出剩余可用来匹配的字符串了，所以可直接结束匹配，得到结论：没有查找到结果。

Javascript 中的实现

以下是来自 trekhleb/javascript-algorithms 中 JavaScript 版本的 KMP 算法实现：

相关教程：Javascript视频教程

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif">//**<br/> * @see https://www.youtube.com/watch?v=GTJr8OvyEVQ<br/> * @param {string} word<br/> * @return {number[]}<br/> */<br/>function buildPatternTable(word) {<br/>  const patternTable = [0];<br/>  let prefixIndex = 0;<br/>  let suffixIndex = 1;<br/><br/>  while (suffixIndex < word.length) {<br/>    if (word[prefixIndex] === word[suffixIndex]) {<br/>      patternTable[suffixIndex] = prefixIndex + 1;<br/>      suffixIndex += 1;<br/>      prefixIndex += 1;<br/>    } else if (prefixIndex === 0) {<br/>      patternTable[suffixIndex] = 0;<br/>      suffixIndex += 1;</span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif"><br/></span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif">    } else {<br/>      prefixIndex = patternTable[prefixIndex - 1];<br/>    }<br/>  }<br/><br/>  return patternTable;<br/>}<br/><br/>/**<br/> * @param {string} text<br/> * @param {string} word<br/> * @return {number}<br/> */<br/>export default function knuthMorrisPratt(text, word) {<br/>  if (word.length === 0) {<br/>    return 0;</span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¾®è½¯é›…é»‘, Tahoma, Arial, sans-serif"><br/>  }<br/><br/>  let textIndex = 0;<br/>  let wordIndex = 0;<br/><br/>  const patternTable = buildPatternTable(word);<br/><br/>  while (textIndex < text.length) {<br/>    if (text[textIndex] === word[wordIndex]) {<br/>      // We&#39;ve found a match.<br/>      if (wordIndex === word.length - 1) {<br/>        return (textIndex - word.length) + 1;<br/>      }<br/>      wordIndex += 1;<br/>      textIndex += 1;<br/>    } else if (wordIndex > 0) {<br/>      wordIndex = patternTable[wordIndex - 1];<br/>    } else {<br/>      wordIndex = 0;<br/>      textIndex += 1;<br/>    }<br/>  }<br/><br/>  return -1;<br/>}<br/></span>

时间复杂度

因为算法中涉及两部分字符串的线性对比，其时间复杂度为两字符串长度之和，假设需要搜索的关键词长度为 k，总字符串长度为 m，则时间复杂度为 O(k+m)。

以上是带你轻松理解KMP算法的详细内容。更多信息请关注PHP中文网其他相关文章！

声明

本文转载于：博客园。如有侵权，请联系admin@php.cn删除

JavaScript是用C编写的吗？检查证据Apr 25, 2025 am 12:15 AM

是的，JavaScript的引擎核心是用C语言编写的。1）C语言提供了高效性能和底层控制，适合JavaScript引擎的开发。2）以V8引擎为例，其核心用C 编写，结合了C的效率和面向对象特性。3）JavaScript引擎的工作原理包括解析、编译和执行，C语言在这些过程中发挥关键作用。

JavaScript的角色：使网络交互和动态Apr 24, 2025 am 12:12 AM

JavaScript是现代网站的核心，因为它增强了网页的交互性和动态性。1)它允许在不刷新页面的情况下改变内容，2)通过DOMAPI操作网页，3)支持复杂的交互效果如动画和拖放，4)优化性能和最佳实践提高用户体验。

C和JavaScript：连接解释Apr 23, 2025 am 12:07 AM

C 和JavaScript通过WebAssembly实现互操作性。1）C 代码编译成WebAssembly模块，引入到JavaScript环境中，增强计算能力。2）在游戏开发中，C 处理物理引擎和图形渲染，JavaScript负责游戏逻辑和用户界面。

从网站到应用程序：JavaScript的不同应用Apr 22, 2025 am 12:02 AM

JavaScript在网站、移动应用、桌面应用和服务器端编程中均有广泛应用。1)在网站开发中，JavaScript与HTML、CSS一起操作DOM，实现动态效果，并支持如jQuery、React等框架。2)通过ReactNative和Ionic，JavaScript用于开发跨平台移动应用。3)Electron框架使JavaScript能构建桌面应用。4)Node.js让JavaScript在服务器端运行，支持高并发请求。

Python vs. JavaScript：比较用例和应用程序Apr 21, 2025 am 12:01 AM

Python更适合数据科学和自动化，JavaScript更适合前端和全栈开发。1.Python在数据科学和机器学习中表现出色，使用NumPy、Pandas等库进行数据处理和建模。2.Python在自动化和脚本编写方面简洁高效。3.JavaScript在前端开发中不可或缺，用于构建动态网页和单页面应用。4.JavaScript通过Node.js在后端开发中发挥作用，支持全栈开发。