A prefix-suffix match occurs when a proper prefix of a character sequence is also one of its suffixes. Its shared length measures the repeated portion. section 5.1
A shared ending and beginning
For XYZXY, the proper prefixes include X and XY, while the proper suffixes include Y and XY. The longest match is XY, with length 2. For 10101, the shared portion is 101, with length 3. section 5.1
In Knuth–Morris–Pratt (KMP), these lengths form the LPS array: a lookup table that helps the search resume after a mismatch without moving the text pointer backward. section 5.1 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 the LPS values as they are built for the pattern aabadc, including mismatches and fallback steps. section 5.1.1
