String Matching Algorithms

KMP

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
LPS Table
Click Play or Step to build LPS table
Complexity: Best/Avg/Worst O(n+m) | Space O(m)

Rabin-Karp

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Algorithm Data
No table for this algorithm
Complexity: Best/Avg/Worst O(n+m) | Space O(1)

Boyer-Moore

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Shift Table
Shift table not visualized
Complexity: Best/Avg/Worst O(n/m) | Space O(m)

Z Algorithm

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Algorithm Data
No table for this algorithm
Complexity: Best/Avg/Worst O(n+m) | Space O(n+m)

Naive String Matching

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Algorithm Data
No table for this algorithm
Complexity: Best/Avg/Worst O(n) | Space O(1)

Aho-Corasick

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Algorithm Data
No table for this algorithm
Complexity: Best/Avg/Worst O(n+m+z) | Space O(m)

Finite Automaton

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Algorithm Data
No table for this algorithm
Complexity: Best/Avg/Worst O(n) | Space O(m|Σ|)

Manacher's Algorithm

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Algorithm Data
No table for this algorithm
Complexity: Best/Avg/Worst O(n) | Space O(n)

Horspool

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Shift Table
Shift table not visualized
Complexity: Best/Avg/Worst O(n/m) | Space O(m)

Suffix Array

Speed
120ms
Input
lorem ipsum dolor sit amet ipsum
Algorithm Data
No table for this algorithm
Complexity: Best/Avg/Worst O(n log n) | Space O(n)