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

Knuth-Morris-Pratt (KMP) Algorithm

Learn how KMP searches for a pattern in linear time by using previously matched information to avoid unnecessary character comparisons.

Explanation

Overview

The Knuth-Morris-Pratt algorithm is an efficient pattern-matching algorithm that searches for a pattern within a text. Instead of restarting the comparison from the beginning of the pattern after every mismatch, it uses information about the pattern's prefixes and suffixes to determine how far the pattern can safely shift.

Key concepts

Prefix and suffix; Longest Proper Prefix which is also a Suffix; Pattern preprocessing; Mismatch handling; Avoiding redundant comparisons; Linear-time pattern matching

Variables

text: The larger string being searched.; pattern: The pattern to locate.; n: The length of the text.; m: The length of the pattern.; i: The current text index.; j: The current pattern index.

Complexity

lpsPreprocessing: O(m) time.; patternSearching: O(n) time.; overall: O(n + m) time.; space: O(m) auxiliary space for the LPS array.

Example

text: ABABDABACDABABCABAB; pattern: ABABCABAB; matchingPosition: 10; explanation: KMP uses previously matched prefix-suffix information to avoid comparing characters that are already known to match.

Pseudocode

function KMP(text, pattern):
lps = buildLPS(pattern)
i = 0
j = 0
matches = []
while i < length(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == length(pattern):
matches.append(i - j)
j = lps[j - 1]
else if i < length(text) and text[i] != pattern[j]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return matches

Applications

Text editors.; Search engines.; DNA sequence matching.; Log analysis.; Exact substring searching.; Pattern detection in data streams.

Variables

Text

The larger string being searched.

Pattern

The pattern to locate.

N

The length of the text.

M

The length of the pattern.

I

The current text index.

J

The current pattern index.

LPS

The Longest Proper Prefix which is also a Suffix array for the pattern.

Example or application

Text

ABABDABACDABABCABAB

Pattern

ABABCABAB

Matching Position

10

Explanation

KMP uses previously matched prefix-suffix information to avoid comparing characters that are already known to match.

Definition

The Knuth-Morris-Pratt algorithm is an efficient pattern-matching algorithm that searches for a pattern within a text. Instead of restarting the comparison from the beginning of the pattern after every mismatch, it uses information about the pattern's prefixes and suffixes to determine how far the pattern can safely shift.

Mathematical Representation

When a mismatch occurs after j matched characters, update j = LPS[j - 1] instead of resetting j to zero, unless the current text character can be matched at the new pattern position.

Algorithm Steps

  • Build the LPS array for the pattern.

  • Initialize text index i and pattern index j to zero.

  • Compare text[i] and pattern[j].

  • If they match, increment both indices.

  • If j reaches the pattern length, record a match and use the LPS value to continue searching.

  • If a mismatch occurs and j is greater than zero, update j using LPS[j - 1].

  • If a mismatch occurs when j is zero, advance the text index.

  • Continue until the text has been processed.

Pseudocode

function KMP(text, pattern):
lps = buildLPS(pattern)
i = 0
j = 0
matches = []
while i < length(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == length(pattern):
matches.append(i - j)
j = lps[j - 1]
else if i < length(text) and text[i] != pattern[j]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return matches

Complexity

Lps Preprocessing

O(m) time.

Pattern Searching

O(n) time.

Overall

O(n + m) time.

Space

O(m) auxiliary space for the LPS array.

Key Concepts

  • Prefix and suffix

  • Longest Proper Prefix which is also a Suffix

  • Pattern preprocessing

  • Mismatch handling

  • Avoiding redundant comparisons

  • Linear-time pattern matching

Advantages

  • Guarantees O(n + m) time for standard exact pattern matching.

  • Does not move backward through the text.

  • Avoids repeated comparisons after mismatches.

  • Works effectively with repetitive patterns.

  • Requires only linear additional memory.

Limitations

  • The LPS preprocessing step requires careful implementation.

  • Understanding mismatch transitions can be challenging for beginners.

  • For some practical text-searching workloads, other algorithms may perform better due to implementation and data characteristics.

Applications

  • Text editors.

  • Search engines.

  • DNA sequence matching.

  • Log analysis.

  • Exact substring searching.

  • Pattern detection in data streams.

Related Topics

  • Longest Prefix-Suffix Array

  • Naive Pattern Matching

  • Z Algorithm

  • String Algorithms

Practice Question

What does KMP use to avoid restarting pattern comparison from index zero after a mismatch?

Practice Answer

The LPS array.

Learning Objectives

  • Explain the central idea and purpose of knuth-morris-pratt (kmp) algorithm.

  • Identify the assumptions, inputs, and conditions relevant to knuth-morris-pratt (kmp) algorithm.

  • Evaluate an application of knuth-morris-pratt (kmp) algorithm 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