liveBook · Manning

LPS array

As explained in Algorithms Every Programmer Should Know

An LPS array stores, for each pattern position, the length of the longest proper prefix that is also a suffix of the pattern prefix ending there.

Imagine searching a long stream for a short pattern. If five characters match and the sixth does not, starting the pattern over throws away useful information. The LPS array lets the Knuth–Morris–Pratt (KMP) algorithm reuse what the partial match already revealed. section 5.0

For each pattern position i, LPS[i] stores the length of the longest proper prefix that is also a suffix of the pattern ending at i. “Proper” means shorter than that whole pattern segment. For example, XYZXY begins and ends with XY, so its final LPS value is 2. section 5.0 section 5.1

Build an array for aabadc

The pattern aabadc produces [0, 1, 0, 1, 0, 0]. At position 1, aa has the one-character prefix and suffix a. At position 2, aab has no matching proper prefix and suffix, so the value returns to 0. The same one-character match appears at position 3. section 5.1.1

Table 5.1 Step-by-Step LPS array construction for "aabadc"
Index (i)
Current char (pattern[i])
Current prefix (length)
Compare against (pattern[length])
Match/Mismatch Action
LPS array
0
a
0
N/A (Base case)
lps[0] = 0.
[0, 0, 0, 0, 0, 0]
1
a
0
pattern[0]=('a')
Match. Increment length to 1. Record lps[1] = 1.
[0, 1, 0, 0, 0, 0]
2
b
1
pattern[1]=('a')
Mismatch. Fallback to length becomes lps[0]
Compare again 'b' vs pattern[0] ('a'). Mismatch. Record lps[2] = 0.
[0, 1, 0, 0, 0, 0]
3
a
0
pattern[0]=('a')
Match. Increment length to 1. Record lps[3] = 1.
[0, 1, 0, 1, 0, 0]
4
d
1
pattern[1]=('a')
Mismatch. Fallback to length becomes lps[0]. Compare again: 'd' vs pattern[0] ('a'). Mismatch. Record lps[4] = 0.
[0, 1, 0, 1, 0, 0]
5
c
0
pattern[0]=('a')
Mismatch. No fallback possible (length is already 0). Record lps[5] = 0.
[0, 1, 0, 1, 0, 0]

Follow each row to see which characters are compared, when the candidate length falls back, and how each value is recorded. section 5.1.1

To construct the array, keep i at the position being filled and length at the current candidate prefix-suffix length:

  • Set LPS[0] to 0 and start i at 1. section 5.1.1
  • If pattern[i] matches pattern[length], increase length, store it at LPS[i], and advance i. section 5.1.1
  • On a mismatch with nonzero length, try the shorter candidate LPS[length − 1] without advancing i. If length is zero, store 0 and advance i. section 5.1.1

During a KMP search, suppose j pattern characters have matched before a mismatch. Set j to LPS[j − 1]: those prefix characters are already accounted for, so compare again at the same text position. If j is already zero and the characters still differ, advance in the text. After a full match, the array also tells the search where to resume. section 5.1.1 section 5.4

Building LPS costs O(m) time and O(m) extra space for a pattern of length m; searching a text of length n then takes O(n), for O(n + m) total time. Keeping the text pointer moving forward suits live log and network-traffic streams. The tradeoff is preprocessing and storage: a pattern such as abcdef has an all-zero LPS array, so it offers no useful fallback and may not justify that overhead. section 5.2.1 section 5.3.1 section 5.3.3 section 5.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through array construction, mismatch handling, complexity, and preprocessing tradeoffs.
Examples
Traces the array [0, 1, 0, 1, 0, 0] for aabadc and contrasts it with all-zero abcdef.
What it assumes
Defines proper prefixes and suffixes before using indexed pattern comparisons and pointer loops.
What you can do after
Build it from scratch for a pattern and use its entries to resume KMP comparisons after mismatches.
How it connects
Connects proper prefixes and suffixes to KMP, naive string matching, and streaming pattern search.

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.