Interviews (FANG): Efficient Pattern Searching in Text using KMP!
Let's explore a magical algorithm called "KMP", that can improve your boring string searching algorithm hahah!
Hello again, brave coder 👨💻! In today’s article, I’m willing to share with you an advanced and magical way of finding patterns in massive text datasets! Most beginner programmers, endlessly search for strings the hard way (brute-force)! Let me introduce you to your new favorite magical algorithm: the Knuth-Morris-Pratt Algorithm, a.k.a. KMP! It's an efficient way to search for patterns in text.
Let’s get started!
What the Huck is KMP?
First of all, KMP stands for Knuth-Morris-Pratt Algorithm, the three fellows that created this algorithm. Now, let’s understand the problem KMP solves.
Imagine you have a massive book 📖, and you're trying to find a single phrase on this book! Seems very hard to do in terms of runtime cost! You could brute-force it by checking every possible position! But that’s too slow 🐌!
KMP is like a magic scroll that skips unnecessary steps using a secret weapon called: prefix tables.
Ready? Let’s break it down!
Level 1: Getting Started
First, let’s clarify what KMP does:
Input:
A text: "LOVELOVELOVELYCODER"
A pattern: "LOVELY"
Output: The index where the pattern starts in the text (index 8 in our example).
Let’s start coding the KMP algorithm step by step, until we get the final version:
function kmpSearch(text, pattern) {
// TODO: Implement the logic!
return -1; // Default return if no match
}
let text = "LOVELOVELOVELYCODER";
let pattern = "LOVELY";
// Should print the starting index or -1 if not found!
console.log(kmpSearch(text, pattern)); Level 2: Adding the Prefix Table
What’s in the Prefix Table?
The prefix table for a pattern contains numbers representing the lengths of the longest proper prefix that is also a suffix up to each position in the pattern.
Proper Prefix: A prefix that is not the entire string. Example: For "ABCD", proper prefixes are "", "A", "AB", "ABC".
Suffix: A substring that ends at the last character. Example: For "ABCD", suffixes are "", "D", "CD", "BCD", "ABCD".
Why Does It Matter?
When a mismatch occurs, the prefix table tells us the furthest valid position in the pattern we can jump to, without rechecking characters that we already know match.
The prefix table helps KMP skip redundant comparisons. Think of it as your cheat sheet for overlapping parts of the pattern!
Step 1: Build the Table
The table stores the length of the longest proper prefix that's also a suffix for every position in the pattern.
Pattern LOVELY
Index 0 1 2 3 4 5
Prefix L O V E L Y
Table 0 0 0 0 1 0PS: At index 4, the prefix
"L"matches the suffix"L", soprefixTable[4] = 1. For all other indices, no prefix matches the suffix, so their values are0.
Here’s how to build it:
Start at 0 for the first character.
Move through the pattern, checking overlaps.
Update the table when overlaps occur.
Now that we understand the prefix table utility, let’s start the fun part (coding):
function buildPrefixTable(pattern) {
let prefixTable = Array(pattern.length).fill(0);
// Tracking the length of the previous longest prefix-suffix
let j = 0;
for (let i = 1; i < pattern.length; i++) {
while (j > 0 && pattern[i] !== pattern[j]) {
j = prefixTable[j - 1];
}
if (pattern[i] === pattern[j]) {
j++;
}
prefixTable[i] = j;
}
return prefixTable;
}
// Example: Build the prefix table for 'LOVELY'
let pattern = "LOVELY";
console.log(buildPrefixTable(pattern)); // [0, 0, 0, 0, 1, 0]Level 3: KMP in Action
With the prefix table in hand, the real magic begins. Instead of brute-forcing, KMP uses the table to jump ahead when mismatches occur.
The Rules:
If characters match, move both pointers forward.
If a mismatch happens, don’t start over! Use the prefix table to adjust the pattern pointer.
Stop when you find the pattern or reach the end of the text.
Let’s code the search function:
function kmpSearch(text, pattern) {
let prefixTable = buildPrefixTable(pattern);
let i = 0; // Pointer for text
let j = 0; // Pointer for pattern
while (i < text.length) {
if (text[i] === pattern[j]) {
i++;
j++;
if (j === pattern.length) {
return i - j; // Found match, return starting index
}
} else {
if (j > 0) {
j = prefixTable[j - 1]; // Use prefix table to jump
} else {
i++; // Move text pointer forward
}
}
}
return -1; // No match found
}Level 4: Let’s Test It !
Let’s run our magical function!
let text = "LOVELOVELOVELYCODER";
let pattern = "LOVELY";
let result = kmpSearch(text, pattern);
console.log(result); // Should print 9🛡️ Explanation:
The algorithm skips redundant checks after a mismatch (thanks to the prefix table).
When "LOVELY" is found at index 9, the search is complete!
Why the Hell KMP is Fast?
Unlike brute force, which can take O(n × m) (where n is text length and m is pattern length), KMP runs in O(n + m).! Why? Because:
Prefix table precomputes overlaps.
No character is checked more than twice.
Wrapping it up!
After reading this article, you must be able to:
🎯 know how to build the prefix table.
🚀 Implement an efficient search with KMP.
From now on, you must use the KMP Algorithm whenever string searching comes your way. Show your searching skills to the world!
That’s it for today’s article, see you in the next one!
🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!
great article