KMP substring search

Medium

Problem

Find every index where the pattern occurs in the text in O(n + m) time, using the KMP failure (longest proper prefix that is also a suffix) table.

Example 1

Input:  text = "ABABDABACDABABCABAB", pattern = "ABABCABAB"
Output: [10]

Also asked as: KMP Algo

Test cases

Case 1

Input:    "ABABDABACDABABCABAB", "ABABCABAB"
Expected: [10]

Case 2

Input:    "aaaa", "aa"
Expected: [0,1,2]

Case 3

Input:    "abc", "d"
Expected: []

Case 4

Input:    "ab", "abc"
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Prefix-function (failure table)

Time O(n + m)Space O(m)

Precompute, for each pattern prefix, the longest proper prefix that is also a suffix. On a mismatch, jump the pattern pointer back using that table instead of restarting.

function kmp(text, pat) {
const m = pat.length;
const lps = Array(m).fill(0);
for (let i = 1, len = 0; i < m; ) {
if (pat[i] === pat[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
const res = [];
for (let i = 0, j = 0; i < text.length; ) {
if (text[i] === pat[j]) { i++; j++; if (j === m) { res.push(i - m); j = lps[j - 1]; } }
else if (j) j = lps[j - 1];
else i++;
}
return res;
}