liveBook · Manning

Pattern shift

As explained in Algorithms Every Programmer Should Know

A pattern shift is the relocation of a search pattern to a later text position after a comparison result determines that earlier positions can be skipped.

In Knuth–Morris–Pratt (KMP) search, a pattern shift moves the pattern forward after a mismatch without restarting the text pointer. The LPS array tells KMP how much of the pattern can still match, so it can skip comparisons already accounted for. section 5.1.1

A mismatch during the search

While searching with the pattern “aabadc,” the comparison reaches a mismatch after several characters match. KMP consults the LPS array to resume with the pattern shifted; the text pointer stays at its current position. In a live stream, this lets the search continue without moving backward through discarded data. section 5.1.1 section 5.2.1

Figure 5.4 The text and the pattern match perfectly till i = 3. At i = 3, the character is ‘x’ and j = 3 is ‘d’, a mismatch occurs. In the LPS array, we look at the previous LPS[j-1] and set that value to j. The right shift of the pattern can be calculated as j - LPS[j-1], which is 3 - 0 spaces towards the right.

See the pattern shift after a mismatch, with the LPS value determining how far the pattern moves. section 5.1.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through LPS construction and pointer movement during mismatches, including multiple shifts and a final match.
Examples
Uses the pattern “aabadc” in a mismatch walkthrough and an error-type search in a live data stream.
What you can do after
Apply KMP’s LPS lookup to resume pattern matching after mismatches while keeping the text pointer moving forward.
How it connects
Connects pattern shifts to Knuth–Morris–Pratt, the LPS array, and string matching.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.