Let you easily understand the KMP algorithm

KMP (The Knuth-Morris-Pratt Algorithm) algorithm is used for string matching to find a given substring from a string. But it's not very easy to understand and master. Understanding the partial matching table in its concept is the key to understanding the KMP algorithm.

The discussion here avoids the obscure logic behind it and focuses on understanding it from its application.

String search

For example, find the abcdg substring from the string abcdef.

Simple solution, we can do this,

• take out the first digit respectively for matching, and if they are the same, take out the second digit.
• If they are different, move the index one bit back, starting from the second digit of the total string, and repeat step one.

The disadvantage of this simple solution is that every time the matching fails, the index is only moved back one position, which has many redundant operations and is not efficient.

In the first round of matching, that is, when the index is 0, we can match the first four characters abcd which are equal, and later find that the desired g is equal to The real e does not match, indicating that the match failed when the index is 0, and we start looking at the index 1, but because we already know the appearance of the first four characters in the total string in the first round of matching , but still need to be matched one by one repeatedly.

Partial Match Table/Partial Match Table

Take a string of length 8abababca, as an example, the partial match table is:

<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>

The value row is the value of the partial matching table.

Subset

For the above example string, if we observe the position where index is 2, then we get a Subset aba, if we observe the position where index is 7, it is obvious that we get the entire string. When the position we observe is different, it means that the subset of the string we are paying attention to is different because the substring has changed.

Prefix & Suffix

For a given string, remove one or more characters from the end, and the remaining part is called the true value of the string Prefix (Proper prefix), hereinafter referred to as prefix. "True" here does not mean "true prefix". Think of the "proper subset" of a set in mathematics. For example, banana, its prefix is:

• <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>
• ##ban<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>
• bana<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>

#Similarly, starting from the header, remove one or more words, and the remaining part is the true suffix of the string (Proper suffix). Or

banana, its suffix is:

• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">anana</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<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>
• ##a<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>
##Partial matching value

It can be seen that all prefixes and suffixes are symmetrical in quantity. Then we can find one from the prefix and match it with the suffix. Let’s not start with Care about the meaning of this match. Take the initial text abababca

as an example.

If we observe the position where index

is 2, the substring is

aba, and its suffixes and suffixes are: Prefix:

a

,
• ab Suffix: ba
,
• a## Change the prefixes in order Match in the suffix. The only substring that can be matched in the suffix list here is a
. Its length is 1, so fill in the observation result in the table and write it down. The matching table matches.

For another example, let’s observe the position where index is 3. The substring obtained at this time is

abab

, and the suffix and suffix at this time are: Prefix: a

,

ab
• , aba Suffix: bab,
ab
• , bAt this time, it can be observed that the matching item is ab
, and the length is 2, which is also consistent with the value in the above partial matching table.

For another example, let’s observe the position where index is 5. At this time, the substring is

ababab

, and the suffix and suffix are: prefix : a

,

ab
• , aba, abab, ababa Suffix: babab,
abab
• , bab, ab, b and then take each of the prefixes The elements are matched with the elements in the suffix, and two matches are finally found,

ab

• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>abab
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"></span>We take the longer abab
, its length is 4.

So now let’s look at the partial matching table above. First, we can understand how its value comes from, and second, we can understand the meaning of its representation, that is, the longest length among all the matches of prefixes and suffixes. The length of that one. When we continue until

index

is 6, the substring is

abababc

. As can be expected, no match is found in the suffix and suffix. Because all prefixes do not contain c, and all suffixes contain c. So the partial match value is 0 at this time. If you continue, you will reach the end of the string, that is, the entire string abababca. It is also expected that since all prefixes start with

a

and all suffixes end with a, the partial match value in this case is at least 1. You will continue to find that because the following suffixes start to have c added, the suffixes all contain ca, and the only prefix that can contain c is abababc, and the length 7 does not match the suffix bababca of equal length. At this point it can be concluded that the matching result is 1 and there is no longer match. Use of partial matching table

Using the above partial matching value, when we perform string search, we don’t have to move only one bit after each failure, but Multiple bits can be moved to remove some redundant matches. There is a formula here as follows:

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)。

The above is the detailed content of Let you easily understand the KMP algorithm. For more information, please follow other related articles on the PHP Chinese website!