KMP Algorithm Knuth-Morris-Pratt

Find all occurrences of pattern in text in O(n+m) time using the failure function to skip redundant comparisons. LC 28, 214, 1392.

Unvisited
Comparing
Match found
Mismatch

Controls

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

Steps