Knuth Morris Pratt Algorithm

What is the KMP algorithm

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

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

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"));

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.