A proper prefix is a contiguous sequence at the exact beginning of a string that is shorter than the whole string. In Knuth–Morris–Pratt string matching, proper prefixes help identify pattern portions that are also suffixes. section 5.0 section 5.0
A proper prefix in a string
“aab” is a proper prefix of “aabad”: it begins the string and is shorter than the whole string. section 5.0
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 how prefix-suffix matches are calculated to build the LPS array for “aabadc.” section 5.1.1
