liveBook · Manning

Prefix-suffix match

As explained in Algorithms Every Programmer Should Know

A prefix-suffix match is an equality between a proper prefix and a suffix of a character sequence, represented by their shared length.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works from small string examples through stepwise LPS construction and mismatch fallback.
Examples
Uses XYZXY and 10101 to illustrate shared portions, then builds LPS values for aabadc.
What it assumes
Introduces proper prefixes and suffixes before using them to identify shared lengths.
What you can do after
Builds an LPS array by recording each position’s longest proper prefix-suffix length.
How it connects
Connects prefix-suffix matches to the LPS array and Knuth–Morris–Pratt string matching.

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.