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
0 stepsPress Run to trace the algorithm one step at a time.