Algorithm | Preprocessing time | Matching time1 |
---|---|---|
Naïve string search algorithm | 0 (no preprocessing) | Θ((n−m+1) m) |
Rabin–Karp string search algorithm | Θ(m) | average Θ(n+m), worst Θ((n−m+1) m) |
Finite-state automaton based search | Θ(m |Σ|) | Θ(n) |
Knuth–Morris–Pratt algorithm | Θ(m) | Θ(n) |
Boyer–Moore string search algorithm | Θ(m + |Σ|) | Ω(n/m), O(nm) |
Bitap algorithm (shift-or, shift-and, Baeza–Yates–Gonnet) | Θ(m + |Σ|) | O(mn) |
Rabin–Karp string search algorithm
Rolling hash.
No comments:
Post a Comment