Knuth–Morris–Pratt Algorithm
Algorithm · Stretch
Step through it: String Matching pattern
Step 1 of 5
Goal: find "abc" inside "ababcab". Slide the pattern along the text and compare letter by letter.
Step 2 of 5
At position 0: a matches, b matches, then c meets a. Mismatch.
Step 3 of 5
The slow way starts over one step later and re-reads letters. Clever methods (KMP and friends) remember that "ab" already matched, so they jump ahead and never re-read the text.
Step 4 of 5
Match found at position 2. The work is about n + m instead of n × m. This family is string matching.
Step 5 of 5
Your turn.
Complexity
Time Complexity
- Time:
O(|W| + |T|)(much faster comparing to trivialO(|W| * |T|))
Space Complexity
- Space:
O(|W|)
The Knuth–Morris–Pratt string searching algorithm (or
KMP algorithm) searches for occurrences of a "word" W
within a main "text string" T by employing the
observation that when a mismatch occurs, the word itself
embodies sufficient information to determine where the
next match could begin, thus bypassing re-examination
of previously matched characters.
Code
/**
* @see https://www.youtube.com/watch?v=GTJr8OvyEVQ
* @param {string} word
* @return {number[]}
*/
function buildPatternTable(word) {
const patternTable = [0];
let prefixIndex = 0;
let suffixIndex = 1;
while (suffixIndex < word.length) {
if (word[prefixIndex] === word[suffixIndex]) {
patternTable[suffixIndex] = prefixIndex + 1;
suffixIndex += 1;
prefixIndex += 1;
} else if (prefixIndex === 0) {
patternTable[suffixIndex] = 0;
suffixIndex += 1;
} else {
prefixIndex = patternTable[prefixIndex - 1];
}
}
return patternTable;
}
/**
* @param {string} text
* @param {string} word
* @return {number}
*/
export default function knuthMorrisPratt(text, word) {
if (word.length === 0) {
return 0;
}
let textIndex = 0;
let wordIndex = 0;
const patternTable = buildPatternTable(word);
while (textIndex < text.length) {
if (text[textIndex] === word[wordIndex]) {
// We've found a match.
if (wordIndex === word.length - 1) {
return (textIndex - word.length) + 1;
}
wordIndex += 1;
textIndex += 1;
} else if (wordIndex > 0) {
wordIndex = patternTable[wordIndex - 1];
} else {
// wordIndex = 0;
textIndex += 1;
}
}
return -1;
}References
Practice
String Matching
- Find the Index of the First Occurrence in a StringEasy
- Repeated Substring PatternEasy
- Is SubsequenceEasy
- Rotate StringEasy
- Longest Palindromic SubstringMedium
- Palindromic SubstringsMedium
- Repeated String MatchMedium
- One Edit DistanceMedium
- Shortest PalindromeHard
- Longest Happy PrefixHard
- Longest Duplicate SubstringHard
- Edit DistanceHard
- Wildcard MatchingHard
Spotted a mistake or something unclear? Report it on GitHub.