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.
Top comments (0)