1. Empty pattern
Match empty pattern at index 0.
if (pattern.length === 0) return 0Typorithm · hard
KMP String Search
▷ Interactive algorithm labkmp-string-searchsearchstringpatternprefix-table
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn KMP String Search
Search Algorithms
KMP String Search uses a prefix table so mismatches do not force the text pointer to move backward.
KMP preprocesses the pattern into an LPS table.
LPS means longest proper prefix that is also a suffix.
When a mismatch happens after some matches, KMP moves the pattern pointer back using the table.
The text pointer never rewinds, so the search runs in O(n + m).
Preparing algorithm lab…
01
Build the LPS table from the pattern.
02
Use i for text and j for pattern.
03
On match, advance both.
04
On mismatch, fallback j with lps.
05
Time is O(n + m).
function kmpSearch(text, pattern) {
if (pattern.length === 0) return 0;
const lps = buildLps(pattern);
let i = 0;
let j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++;
j++;
if (j === pattern.length) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
function buildLps(pattern) {
const lps = Array(pattern.length).fill(0);
let length = 0;
let i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[length]) {
length++;
lps[i] = length;
i++;
} else if (length > 0) {
length = lps[length - 1];
} else {
i++;
}
}
return lps;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Prefix table
Build the table that tells how far the pattern can fall back.
const lps = buildLps(pattern)3. Text and pattern pointers
i scans text and j scans pattern.
let i = 0;
let j = 04. Character match
Advance both pointers on a matching character.
if (text[i] === pattern[j])5. Return start
When j reaches the pattern length, i - j is the start index.
if (j === pattern.length) return i - j6. Fallback
On mismatch, reuse the longest prefix that is also a suffix.
j = lps[j - 1]7. Build LPS
The helper computes fallback lengths for every pattern position.
function buildLps(pattern)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.