concept · INFO-CS-ADS-196Knuth-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.
M
The length of the pattern.
J
The current pattern index.
LPS
The Longest Proper Prefix which is also a Suffix array for the pattern.
Example or application
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.
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.
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