Finding a pattern in text
The naive way to find a pattern inside a text slides the pattern one position at a time and rechecks from scratch on every mismatch. The Knuth Morris Pratt algorithm, or KMP, avoids that wasted work and runs in time proportional to the text length plus the pattern length.
The failure table
KMP precomputes a prefix table, sometimes called the failure function, over the pattern. For each position it records the length of the longest proper prefix of the pattern that is also a suffix ending there.
- This table captures how much of the pattern you already matched that can be reused.
- It is built in one linear pass over the pattern.
Matching without backtracking
When a mismatch occurs after matching some characters, KMP does not move the text pointer backward. Instead it uses the table to shift the pattern so the already matched prefix lines up, then resumes comparing. The text pointer only ever advances, which is why the whole scan stays linear.
The key insight is that a partial match already tells you about the characters, so re comparing them is wasteful. The table encodes exactly how far you can safely jump.
Key idea
KMP builds a prefix failure table so that on a mismatch it shifts the pattern by reusing matched characters, never moving the text pointer backward.