KMP Pattern Matching

Donald Knuth, James Morris & Vaughan Pratt, 1970

The Knuth-Morris-Pratt algorithm preprocesses the pattern to build a failure function (partial match table) that encodes how much of the pattern can be reused after a mismatch. This allows the search to never backtrack in the text, achieving O(n + m) time complexity. The visualization shows character-by-character comparison with the failure table guiding pattern shifts.