String Algorithms — Algorithms

String Matching Visualizer

Knuth-Morris-Pratt

Passo 0 / 0

Speed 100ms

Step Progress 0 / 0

Comparisons 0

Matches Found 0

Status Ready

Text / Pattern

Comparing

Matched

Window / Aux highlight

Match found

Step Explanation

Select an algorithm and press Play to watch the pattern slide across the text.

—

Pseudocode

String Algorithms Algorithms

String Algorithms Algorithm Catalog

4 algorithms in this category. Click any card for detailed analysis.

Rabin-Karp

Unstable

Rabin-Karp hashes the pattern and every length-m window of the text using a rolling hash, comparing hashes first. Only when a hash collision occurs does it verify the actual characters, so most windows are skipped in constant time.

Ideal Use: Use Rabin-Karp when you need to search for multiple patterns at once (each window hash can be compared against many pattern hashes), or when the text is dominated by rare hash collisions.

Best

O(n + m)

Worst

O(n·m)

Space

O(1)

Implementation Difficulty

★ ★ ☆ ☆ ☆ 2/5

Elementary

Graph algorithm — interactive visualization

Inspect & Visualize

Knuth-Morris-Pratt

Unstable

KMP finds all occurrences of a pattern in a text in linear time by precomputing an LPS (longest proper prefix-suffix) table. When a mismatch occurs, the pattern shifts by a known safe amount instead of restarting the comparison.

Ideal Use: Use KMP when you need all occurrences of a fixed pattern in a large text and want guaranteed linear worst-case behavior — no backtracking on the text pointer.

Best

O(n)

Worst

O(n + m)

Space

O(m)

Implementation Difficulty

★ ★ ★ ☆ ☆ 3/5

Intermediate

Graph algorithm — interactive visualization

Inspect & Visualize

Z-Algorithm

Unstable

The Z-algorithm builds a Z-array over "pattern$text": z[i] is the length of the longest substring starting at i that matches a prefix of the string. Every position where z[i] equals the pattern length marks an occurrence.

Ideal Use: Use the Z-algorithm when you want a compact linear-time pattern matcher that is easy to understand — the Z-array is also useful for other prefix-matching problems.

Best

O(n)

Worst

O(n)

Space

O(n)

Implementation Difficulty

★ ★ ★ ☆ ☆ 3/5

Intermediate

Graph algorithm — interactive visualization

Inspect & Visualize

Boyer-Moore

Unstable

Boyer-Moore scans the pattern right-to-left and shifts the window using the last-occurrence (bad-character) rule and the good-suffix rule. When the text alphabet is large, most characters fail on the first probe and the pattern jumps quickly.

Ideal Use: Use for fast substring search over large alphabets — text editors, grep-style tools, and intrusion/pattern detection where the pattern is much shorter than the text.

Best

O(n/m)

Worst

O(nm)

Space

O(m)

Implementation Difficulty

★ ★ ★ ☆ ☆ 3/5

Intermediate

Graph algorithm — interactive visualization

Inspect & Visualize

String Complexity Matrix

Complexity & Performance Tradeoffs

Side-by-side comparison of Big-O time and space complexity characteristics across string algorithms.

Algorithm	Best Time	Average Time	Worst Time	Space Complexity	Stability
Knuth-Morris-Pratt	O(n)	O(n)	O(n + m)	O(m)	Unstable
Rabin-Karp	O(n + m)	O(n + m)	O(n·m)	O(1)	Unstable
Z-Algorithm	O(n)	O(n)	O(n)	O(n)	Unstable
Boyer-Moore	O(n/m)	O(n)	O(nm)	O(m)	Unstable