The naive search tries every offset and re-compares, so it can reach O(n*m) (for example text "aaaa...a" and pattern "aaab"). KMP leverages the information accumulated: after k matching characters, we already know what the last characters were In the text — they are exactly pattern[:k].

The failure array fail[i] is the length of the longest prefix-suffix of pattern[:i+1]. If the match breaks after k characters, the next shift that could succeed leaves us with fail[k-1] matching characters — so it is enough to update k and continue from the same character in the text, without going back.

Building the array is essentially running the pattern's own algorithm on itself, which is why the two steps look almost identical.

k = fail[k-1] after a full match — and not k = 0 - is what allows To catch overlapping occurrences like in "aaaaa".

Complexity: O(n + m) time. Even though there's an inner while loop, Every iteration of it decreases k, and k increases at most once for each character — so the total number of backtracks is bounded by n. Space O(m).

loading…

loading…