Senior LevelData Structures & Algorithms
How do KMP and Z-Algorithm achieve O(N+M) pattern matching?
ā Interview Prompt: Explain KMP failure function and Z-Array pattern matching, both achieving O(N+M) vs naive O(NM) string search.
Naive Pattern Matching: $O(NM)$
For each position in text, compare all $M$ characters of the pattern.
KMP (Knuth-Morris-Pratt): $O(N + M)$
Precompute the LPS (Longest Proper Prefix which is also Suffix) array for the pattern in $O(M)$. On mismatch, use LPS to skip characters already matched ā never moving the text pointer backwards!
Z-Algorithm: $O(N + M)$
Build the Z-array for the concatenated string pattern + '#' + text. Z[i] = length of the longest substring starting at i that matches a prefix of the string. Pattern found where Z[i] === M.
Code Implementation Example
typescript
// KMP Pattern Search ā O(N+M)
function kmpSearch(text: string, pattern: string): number[] {
const lps = buildLPS(pattern);
const matches: number[] = [];
let j = 0;
for (let i = 0; i < text.length; ) {
if (text[i] === pattern[j]) { i++; j++; }
if (j === pattern.length) {
matches.push(i - j);
j = lps[j - 1];
} else if (i < text.length && text[i] !== pattern[j]) {
j > 0 ? j = lps[j - 1] : i++;
}
}
return matches;
}
function buildLPS(p: string): number[] {
const lps = new Array(p.length).fill(0);
let len = 0, i = 1;
while (i < p.length) {
if (p[i] === p[len]) lps[i++] = ++len;
else len > 0 ? len = lps[len - 1] : lps[i++] = 0;
}
return lps;
}š”KMP string matching with LPS failure function ā O(N+M).
šÆ Interview Key Takeaway
KMP and Z-Algorithm are O(N+M) pattern matchers vs O(NM) naive. KMP uses the LPS (failure function); Z uses the Z-array. Both avoid redundant comparisons.
#DSA#KMP#Z-Algorithm#String Matching#Senior
Back to all Data Structures & Algorithms Questionsā