DEV Community

Cover image for Knuth Morris Pratt Algorithm
Arthur David L
Arthur David L

Posted on • Updated on

Knuth Morris Pratt Algorithm

What is the KMP algorithm

Image description

The KMP algorithm is used has a string-matching algorithm, if you want to find the starting index m in string S[] that matches the search word W[]. It is very effective to match string pattern and has an O(n) time complexity and worst case scenario O(m) time complexity.
Brute force solutions would be O(n*m) complexity, KMP O(n+m)

The space complexity is O(m) due to a pre-processing of a function that sets a table.

Example

The first step is to create a table. However before coding the table.

Explanations:

Here a table:
i
+---+---+---+---+---+---+---+---+
| a | b | c | a | b | a | b | c |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
k

The first line represents a string and the second line a sub-string(pattern).

The first line is called i.
The second line is called k.

The line i has a recurrent pattern which is abc.

We can define a pattern as prefix and suffix.

Prefix : a,ab,abc.
Suffix: c, bc, abc.

One prefix is matching a suffix: 'abc'.

If encountering 'abc' twice in a table then:
a: 1, b:2, c:3

Simple Table:
Pattern: 'aab'
+---+---+---+---+---+---+---+---+
| a | a | b | a | b | a | a | b |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+

Complex table

+---+---+---+---+---+---+---+---+---+---+
| a | b | c | a | b | a | x | a | b | c |
+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+

We have a pattern 'abc'.
Any character that is not included in our pattern will be 0.
Characters included in the pattern('abc') are respectively are index
Index 3,4 'ab' a:1,b:2.
Second match at index 8,9,10 'abc'. a:1,b:2,c:3.

That's how we define a table to set up the algorithm. We simply match the prefix and suffix from a table and set a value according to the pattern.

Coding the table

function Table(a) {
  // create an array from index 0
  const table = [0];
  // define i for looping trough table
  // define j = length prefix and suffix
  let i = 1;
  let k = 0;
  while (i < a.length) {
    // if character match them increase i and set k equal to i;
    if (a[i] === a[k]) {
      k += 1;
      table[i] = k;
      i += 1;
    // if k is greater than 0 and  
     characters don't match 
    // will reset k to previous index table -1 then while loop again to compare next i from k 
    } else if (k > 0) {
      k = table[k - 1];
    // no character match and k is equal to 0 then increment i to check the next character
    } else {
      table[i] = 0;
      i += 1;
    }
  }
  return table;
}
Enter fullscreen mode Exit fullscreen mode

The easiest way to understand how to table is working is to watch the tables above and reading the code at the same time.

Finishing the Algorithm

const strStr = (string, subString) => {
  // filter out if string is empty = ''
  if (subString === "") return 0;
  // build table from Table function
  const Table = buildTable(subString);
  // create our variable k & i
  i = 0;
  k = 0;
  // we loop trough both string and substring
  while (i < string.length && j < subString.length) {
    // if characters match, increse index by one for both string and continue looping
    if (string[i] === subString[k]) {
      i += 1;
      k += 1;
      // if no match return k to previous index k -1
    } else if (j > 0) {
      k = buildTable[k - 1];
      // if no match and k = 0, increment
    } else {
      i += 1;
    }
    // when we got sutsring into string return -1
    if (k === subString.length) return i - k;
  }
  return -1;
};
Enter fullscreen mode Exit fullscreen mode

Bonus naive solution


function stringSearch(string, pattern) {
  let count = 0;
  for (let i = 0; i < string.length; i++) {
    for (let j = 0; j < pattern.length; j++) {
      if (pattern[j] !== string[i + j]) break;
      if (j === pattern.length - 1) {
        console.log(i)
        count++;  
      } 
    }
  }
  return count;
}

console.log(stringSearch("akgjfjhuyutomatokajkhgsvkjrtomato", "tomato"));
Enter fullscreen mode Exit fullscreen mode

Conclusion

You can test your skills for the KMP algorithm with leetcode question n'28.
shorturl.at/bdD35

Feel free to @ me on Twitter with your opinion & feedback about my article; Constructive feedback is always welcome.

Discussion (0)