String AlgorithmsAdvanced

KMP String Matching

Knuth-Morris-Pratt algorithm for efficient pattern matching in strings. Uses a failure function (LPS array) to skip unnecessary comparisons, achieving O(n+m) time complexity. Essential for text search, DNA sequence analysis, and plagiarism detection.

#string#pattern-matching#preprocessing#text-search

Complexity Analysis

Time (Average)

O(n + m)

Expected case performance

Space

O(m)

Memory requirements

Time (Best)

O(n)

Best case performance

Time (Worst)

O(n + m)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 32•Section 32.4

Presets:

Text

Pattern

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in String Algorithms

Boyer-Moore String Matching

Advanced

Efficient string searching algorithm using bad character and good suffix heuristics. Compares pattern from right to left, allowing large jumps on mismatch. Achieves sublinear time in practice, making it one of the fastest string matching algorithms.

O(n)

O(m + σ)

stringpattern-matching

Start Learning

Back to String Algorithms