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
