liveBook · Manning

Proper prefix

As explained in Algorithms Every Programmer Should Know

A proper prefix is a sequence at the beginning of a string that is strictly shorter than the entire string.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines proper prefixes and demonstrates their role in constructing KMP's LPS array.
Examples
Uses “aab” as a proper prefix of “aabad” and constructs an LPS array for “aabadc.”
What you can do after
Understand how proper-prefix matches contribute to LPS values used to shift a pattern after mismatches.
How it connects
Connects proper prefixes to proper suffixes, the LPS array, and Knuth–Morris–Pratt string matching.

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.