KMP substring search
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: []
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;}