✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-197

Longest 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

Pattern

ABABCABAB

Lps Array

  • 0

  • 0

  • 1

  • 2

  • 0

  • 1

  • 2

  • 3

  • 4

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.

Key Concepts

  • Proper prefix

  • Suffix

  • Longest matching prefix and suffix

  • Prefix fallback

  • Pattern preprocessing

  • KMP mismatch handling

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.

Applications

  • KMP pattern matching.

  • Repeated substring analysis.

  • Periodicity detection.

  • Prefix-suffix analysis.

  • String algorithm education.

Related Topics

  • KMP Algorithm

  • Z Algorithm

  • String Prefixes and Suffixes

  • Pattern Matching

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