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
