String Matching Algorithms
KMP
Speed120ms
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
Speed120ms
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
Speed120ms
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
Speed120ms
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
Speed120ms
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
Speed120ms
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
Speed120ms
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
Speed120ms
Input
lorem ipsum dolor sit amet ipsum
Algorithm Data
No table for this algorithm
Complexity: Best/Avg/Worst O(n) | Space O(n)
Horspool
Speed120ms
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
Speed120ms
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)