Searching for a pattern in a text is easy — naive scanning compares every window, but that’s O(n·m) and repeats work. KMP finds all occurrences in linear time by remembering how much of the pattern already matched. When a mismatch happens, it never re-examines matched text; a precomputed table says exactly how far to shift the pattern instead of restarting from scratch.

How It Works

1. Build LPS — for each prefix of the pattern, store the length of its longest proper prefix that is also a suffix. This is the “memory” of the algorithm.
2. Match phase — scan the text with a pointer that never moves backward.
3. On mismatch — instead of resetting, jump j = LPS[j-1]; the already-matched prefix tells you how much can be reused.
4. On full match — record the position, then set j = LPS[j-1] and keep scanning for more occurrences.

Key Insight

The LPS table answers: “I matched up to pattern position j and the text char differs — how much of my current match is still usable?” Because it’s the longest proper prefix that is also a suffix, the shifted pattern still aligns with everything already scanned. The text pointer only moves forward, and j only decreases through LPS jumps — together that bounds the total work at O(n + m).

Worked Example

The visualizer matches pattern P = ABABCABAB in text T = ABABDABACDABABCABAB.

The LPS table for the pattern: [0, 0, 1, 2, 0, 1, 2, 3, 4].

Watch the mismatch at the C vs D clash:

  T: A B A B D A B A C D A B A B C A B A B
  P: A B A B C A B A B
           ↑ j = 4, T = D, P = C → mismatch

LPS[3] = 2, so the pattern shifts by 2 and comparison resumes from P[2] — the text pointer never goes back. Scanning continues to position 10, where the full match ABABCABAB is reported. Total work stays linear even though the pattern appears only once.

Edge Cases & Pitfalls

• Overlapping occurrences: after a match, set j = LPS[m-1] — otherwise overlapping hits are missed.
• No prefix-suffix overlap: LPS = 0 means the pattern fully shifts; the text pointer still doesn’t move back.
• Pattern longer than text: trivially no matches; guard against indexing errors.
• LPS off-by-one: it’s the proper prefix-suffix — a full-length prefix would defeat the shift.
• Empty pattern: by convention matches everywhere or nowhere; define behavior explicitly.

Comparison: KMP vs Other Matchers

Applications

• Text editors — grep and editor search use linear matchers
• Pattern in DNA/protein sequences — long exact patterns
• Parsers — lexical analysis locating tokens efficiently

Practice Trajectory

1. Build the LPS table for ABABCABAB by hand and confirm [0,0,1,2,0,1,2,3,4].
2. Trace the visualizer’s mismatch at the D and verify the shift of 2.
3. Explain why the text pointer never needs to move backward.
4. Confirm the single match at position 10 by hand.
5. Extend the scan to find overlapping occurrences and note the j = LPS[m-1] rule.