KMP Search Algorithm

KMP Search Algorithm Visually

An efficient string searching algorithm that searches for occurrences of a pattern string within a text string.

String Matching Pattern Matching Time Complexity O(n + m) Space Complexity O(m) Advanced Level
KMP Search Controls
comparisons: 0
Steps: 0
Time: 0ms
Simulation Modes
Text Presets
Performance Analysis

Algorithm Status

Ready
Progress 0%

Text Visualization

Search Pattern
LPS (Longest Prefix Suffix) Array

About KMP Search

The Knuth-Morris-Pratt (KMP) algorithm is a string searching algorithm that searches for occurrences of a "pattern" within a main "text" string. It uses the observation that when a mismatch occurs, the pattern itself contains enough information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

Time Complexity
O(n + m)
Worst Case
Space Complexity
O(m)
Auxiliary

Search Pattern

Current Pattern: ABABCABCABCABC

Algorithm Comparison

KMP Search
O(n + m)
Linear Time
Naive Search
O(n × m)
Quadratic Time
Boyer-Moore
O(n + m)
Best Case O(n/m)

Execution Log

Operation Log
KMP search visualization initialized
Enter text and pattern to begin