KMPアルゴリズムを簡単に理解できるようにする

KMP (Knuth-Morris-Pratt Algorithm) アルゴリズムは、文字列から特定の部分文字列を見つけるための文字列マッチングに使用されます。しかし、それを理解して習得するのはそれほど簡単ではありません。部分一致テーブルの概念を理解することが、KMP アルゴリズムを理解する鍵となります。

ここでの議論は、その背後にあるあいまいなロジックを避け、その応用から理解することに焦点を当てています。

文字列検索

たとえば、文字列 abcdef から部分文字列 abcdg を検索します。

簡単な解決策です。

• 最初の桁をそれぞれ取り出して照合し、それらが同じ場合は 2 番目の桁を取り出します。
• それらが異なる場合は、合計文字列の 2 桁目から開始してインデックスを 1 ビット後ろに移動し、ステップ 1 を繰り返します。

この単純なソリューションの欠点は、マッチングが失敗するたびにインデックスが 1 位置だけ戻されるため、冗長な操作が多く効率的ではないことです。

マッチングの最初のラウンド、つまりインデックスが 0 の場合、等しい最初の 4 文字 abcd とマッチングでき、その後、目的の g# が見つかります。 ## は次と等しい。 実際の e は一致しない。これは、インデックスが 0 の場合にマッチングが失敗したことを示しており、インデックス 1 から調べ始めますが、最初の 4 文字の出現はすでにわかっているためです。最初の照合ラウンドでは合計文字列ですが、それでも 1 つずつ繰り返し照合する必要があります。

部分一致テーブル/部分一致テーブル

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 である位置を観察すると、文字列全体を取得していることは明らかです。観察する位置が異なる場合は、部分文字列が変更されているため、注目している文字列の部分集合が異なることを意味します。

プレフィックスとサフィックス

banana、そのプレフィックスは次のとおりです:

• b<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>
• ba<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>
• バナ<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>
• banan<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>
#同様に、ヘッダーから始めて 1 つ以上の単語を削除し、残りの部分が文字列の真の接尾辞 (適切な接尾辞) になります。または

、そのサフィックスは: <ul> <li><code style="white-space: nowrap;"><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">アナ</span>

すべてのプレフィックスとサフィックスが数量的に対称であることがわかります。次に、プレフィックスから 1 つを見つけて、それをサフィックスと照合します。この試合の意味。最初のテキスト abababca を例として取り上げます。

index が 2 である位置を観察すると、部分文字列は

で、その接尾辞と接尾辞は次のようになります。 プレフィックス: a

ab
• サフィックス: ba、
a
• ## プレフィックスを順番に変更します接尾辞が一致します。ここで接尾辞リストで一致できる部分文字列は a だけです。長さは 1 なので、観測結果を表に記入して書き留めます。一致する表は一致します。

index が 3 である位置を観察してみましょう。このとき得られる部分文字列は abab

プレフィックス: a、

、
• aba サフィックス: bab、ab
,
• bこの時点で、一致する項目は ab で、長さは 2 であることがわかります。は、上記の部分一致テーブルの値とも一致します。

index が 5 である位置を観察してみましょう。このとき、部分文字列は ababab

プレフィックス : a、ab

aba
• 、abab、ababa サフィックス: babab、abab、
bab
• 、ab、b# # その後、それぞれのプレフィックスを取得します。要素はサフィックス内の要素と照合され、最終的に 2 つの一致が見つかります。 #abab

abab
• を使用し、その長さは 4 です。 <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">それでは、上の部分一致テーブルを見てみましょう。まず、その値がどのように由来するかを理解でき、次に、その表現の意味、つまり、すべての一致の中で最も長い長さを理解できます。プレフィックスとサフィックスの長さ。 </span>
index
• が 6 になるまで続けると、部分文字列は abababc<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"> となり、予想のとおり、接尾辞と接尾辞に一致するものは見つかりません。すべてのプレフィックスに </span>c が含まれるわけではなく、すべてのサフィックスに
c

続行すると、文字列の終わり、つまり文字列 abababca

a

a で終わるため、この場合の部分一致値は少なくとも 1 であることが予想されます。次のサフィックスには c が追加され始めているため、すべてのサフィックスには ca が含まれており、c を含むことができる唯一のプレフィックスは であることがわかります。 abababc

bababca と一致しません。この時点で、一致結果は 1 であり、もう一致はないと結論付けることができます。 部分一致テーブルの使用上記の部分一致値を使用すると、文字列検索を実行するときに、失敗するたびに 1 ビットだけを移動する必要がなくなります。ただし、複数のビットを移動して、冗長な一致を削除することができます。ここには次のような式があります: 長さpartial_match_lengthの部分一致が見つかり、table[partial_match_length] > 1の場合、partial_match_length - table[partial_match_length - 1]をスキップできます。文字。#

如果匹配过程中，匹配到了部分值为 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)。