A+DS

KMP String Search

Never re-compare a character you already matched.

The Knuth-Morris-Pratt (KMP) algorithm searches for a pattern in a text by pre-computing a "failure function" (LPS table) that tells it how far to shift the pattern on a mismatch, avoiding redundant comparisons. It achieves O(n + m) time regardless of the input.

  Text:    A B A B D A B A B C A B A B
  Pattern: A B A B C
                   ↑ mismatch at C vs D

  LPS table: [0, 0, 1, 2, 0]
  Shift pattern by LPS[3] = 2:

  Text:    A B A B D A B A B C A B A B
  Pattern:     A B A B C
  No backtracking in text!

How it works

  1. 1Build the LPS (Longest Proper Prefix-Suffix) table for the pattern
  2. 2Slide the pattern along the text, comparing characters
  3. 3On a match, advance both pointers
  4. 4On a mismatch, use the LPS to shift the pattern without backtracking in the text

Loading...