Algorithms and data structures · Intermediate

KMP: reuse a matched prefix after a mismatch

Build prefix-function fallback information to search without moving backward through the text and retain overlapping matches.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Use matched length as the state
  2. Trace a fallback for ababac
  3. Retain overlaps and bound total work
  4. Specify character and empty-pattern semantics
  5. Ask Logeia about this articleCheck your understanding

Use matched length as the state

KMP preprocesses a pattern of length m and scans a text of length n in one direction. In the prefix-function version, π[i] is the longest proper prefix of the pattern prefix ending at i that is also its suffix. During searching, state j records how many pattern characters match the current text suffix. On a mismatch, this earlier match contains useful information: part of its suffix may also be a pattern prefix. The algorithm reuses that relationship instead of restarting comparisons from an earlier text position or discarding all of the matched structure.

Trace a fallback for ababac

The prefix-function values for ababac are [0,0,1,2,3,0]. Suppose ababa has matched and the next text character is b rather than the expected c. From j=5, fall back to π[4]=3 and compare that same text character with the b at pattern position 3. The matched text suffix aba is also the pattern prefix aba, so those three characters remain useful. This differs from resetting the text position and trying every character again. The fallback length is derived from a precisely defined array rather than selected heuristically.

Retain overlaps and bound total work

Pattern aba occurs in ababa at text positions 0 and 2. After a complete match, falling back to π[m−1] preserves the final a as the start of a possible overlapping match. Prefix-function construction and searching both have linear amortized work: matched length can increase only a bounded number of times, and its decreases are charged against those increases. The time bound is O(n+m), with O(m) auxiliary storage. Reporting all occurrences also incurs output cost. Counting a mismatch loop in isolation misses the fact that the text index never moves backward.

Specify character and empty-pattern semantics

An API must decide whether an empty pattern matches every boundary or is invalid input. Byte positions, Unicode code-point positions and language-specific code-unit indices are different quantities. Case folding or normalization changes the searched sequence and may require a mapping back to original text positions. KMP also has deterministic-automaton formulations storing transitions for alphabet symbols. Their preprocessing space differs from the prefix-array version described here. Name the formulation when comparing resource use, and test empty input, repeated symbols, a longer pattern than the text and overlapping matches rather than only one ordinary successful occurrence.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path