帶你輕鬆理解KMP演算法

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，其前綴有：

• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">b</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">ba</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">ban</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">#bana</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">banan</span>

同理，從首部開始，去掉一個或多個字條，剩下的部分是該字串的真後綴（Proper suffix）。還是 banana，其後綴有：

• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">anana</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">nana</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>
• #nana<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>
• ana<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>

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<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>##然後拿前綴中每個元素與後綴中的元素進行匹配，最後找出有兩個匹配項，
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>#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 - tableleial_m ######

如果匹配过程中，匹配到了部分值为 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中文網其他相關文章！