| 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