concept · INFO-CS-ADS-197Longest Prefix-Suffix (LPS) Array
Understand how the LPS array records the longest proper prefix that is also a suffix for every prefix of a pattern, enabling efficient KMP matching.
Explanation
Overview
The Longest Prefix-Suffix array is an auxiliary array used by the KMP pattern-matching algorithm. Each entry stores the length of the longest proper prefix of the pattern prefix that is also a suffix of that same prefix. A proper prefix cannot be equal to the entire string.
Key concepts
Proper prefix; Suffix; Longest matching prefix and suffix; Prefix fallback; Pattern preprocessing; KMP mismatch handling
Variables
pattern: The string used to construct the LPS array.; i: The current index being processed.; length: The length of the currently matched proper prefix-suffix.; LPS[i]: The longest proper prefix-suffix length for the pattern ending at index i.
Complexity
time: O(m), because each pattern position is processed with efficient fallback.; space: O(m) for the LPS array.; variables: m is the length of the pattern.
Example
pattern: ABABCABAB; lpsArray: 0; 0; explanation: For the prefix ABAB at index 3, AB is both a proper prefix and a suffix, so its LPS value is 2. For the complete pattern, ABAB is the longest proper prefix that is also a suffix, giving a value of 4.
Pseudocode
function buildLPS(pattern):
m = length(pattern)
lps = array of size m filled with 0
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else if length > 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
Applications
KMP pattern matching.; Repeated substring analysis.; Periodicity detection.; Prefix-suffix analysis.; String algorithm education.
Variables
Pattern
The string used to construct the LPS array.
I
The current index being processed.
Length
The length of the currently matched proper prefix-suffix.
LPS[i]
The longest proper prefix-suffix length for the pattern ending at index i.
Example or application
Explanation
For the prefix ABAB at index 3, AB is both a proper prefix and a suffix, so its LPS value is 2. For the complete pattern, ABAB is the longest proper prefix that is also a suffix, giving a value of 4.
Definition
The Longest Prefix-Suffix array is an auxiliary array used by the KMP pattern-matching algorithm. Each entry stores the length of the longest proper prefix of the pattern prefix that is also a suffix of that same prefix. A proper prefix cannot be equal to the entire string.
Mathematical Representation
LPS[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i].
Algorithm Steps
Initialize the first LPS value to zero.
Set the current matched-prefix length to zero.
Compare the current pattern character with the character at the matched-prefix position.
If they match, increase the matched-prefix length and store it in the current LPS entry.
If they do not match and the matched-prefix length is positive, fall back to the previous LPS value.
If they do not match and the matched-prefix length is zero, store zero and move forward.
Continue until every pattern position has an LPS value.
Pseudocode
function buildLPS(pattern):
m = length(pattern)
lps = array of size m filled with 0
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else if length > 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
Complexity
Time
O(m), because each pattern position is processed with efficient fallback.
Space
O(m) for the LPS array.
Variables
m is the length of the pattern.
Advantages
Prevents repeated comparisons in KMP.
Can be computed in linear time.
Uses information already present in the pattern.
Makes efficient pattern searching possible.
Limitations
The meaning of proper prefix and suffix must be understood precisely.
LPS values are specific to the exact pattern.
Incorrect fallback logic can cause missed matches or incorrect results.
The LPS array alone does not perform the complete pattern search.
Practice Question
Find the LPS array for the pattern AABA.
Practice Answer
[0, 1, 0, 1].
Learning Objectives
Explain the central idea and purpose of longest prefix-suffix (lps) array.
Identify the assumptions, inputs, and conditions relevant to longest prefix-suffix (lps) array.
Evaluate an application of longest prefix-suffix (lps) array for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- String Algorithms and Pattern Matching
Suggest a correction or source · More in Algorithms & Data Structures