FoundationSource checked

Knuth-Morris-Pratt

Finds pattern matches in text by using a prefix table to skip redundant comparisons.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Intermediate
Family: Prefix Function Matching
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 17
Code example: Ready
Visualization: Ready
Aliases: KMP

Overview

Knuth-Morris-Pratt preprocessing records how much of the pattern is also a suffix of the matched prefix. On a mismatch, the search resumes from that prefix length instead of restarting from scratch.

Core Concepts

prefix tablebordermismatch fallbacklinear search

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n + m)

Average

O(n + m)

Worst

O(n + m)

Space

O(m)

When to Use

Use it for exact string matching with guaranteed linear time.
Use it when repeated partial matches make naive backtracking expensive.
Use it when the pattern can be preprocessed once and searched through a text.

When Not to Use

Avoid it when a simple library substring search is enough and implementation complexity is not worth it.
Avoid it for approximate matching or regular-expression semantics.
Avoid it when many patterns must be searched at once; use a multi-pattern method instead.

What It Does

Builds a prefix table
Skips redundant comparisons

Use Cases

Exact string search
Streaming text matching
Pattern matching education

Inputs

Text
Pattern

Outputs

Match positions

Key Formulas (1)

Prefix length

prefix_[i] = length of longest proper prefix that is also a suffix ending at i

prefix[i] = length of longest proper prefix that is also a suffix ending at i

Stores the fallback match length after a mismatch.

Pseudocode

1.Build a table of longest proper prefix matches for the pattern
2.Scan the text with a pattern index
3.Advance both indexes on a character match
4.Use the prefix table to shift after a mismatch
5.Record matches when the pattern index reaches the end

Canonical Example

Input: text = "abababca", pattern = "ababca"
Output: match at index 2
Explanation: The prefix table lets the search reuse the already matched "abab" prefix after a mismatch.

Implementation Notes

Test the prefix table separately from the text search.
After a full match, continue from the prefix length of the full pattern to find overlaps.
Keep text and pattern indices distinct.