Content deleted Content added
m Reverted 1 edit by 37.34.248.21 (talk) to last revision by Smasongarrison Tags: Twinkle Undo Disambiguation links added |
BNDM algorithm's matching complexity is not O(n), it's the same as for the Boyer-Moore - Omega(n/m) at best, O(n*m) at worst. https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf |
||
Line 97:
! Backward Non-Deterministic [[Directed acyclic word graph|DAWG]] Matching (BNDM)<ref>{{cite journal |last1=Navarro |first1=Gonzalo |last2=Raffinot |first2=Mathieu |title=A bit-parallel approach to suffix automata: Fast extended string matching |journal=Combinatorial Pattern Matching |date=1998 |volume=1448 |pages=14–33 |doi=10.1007/bfb0030778 |url=https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf |publisher=Springer Berlin Heidelberg |series=Lecture Notes in Computer Science |isbn=978-3-540-64739-3 |access-date=2019-11-22 |archive-date=2019-01-05 |archive-url=https://web.archive.org/web/20190105101910/https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf |url-status=live }}</ref>{{ref|fuzzy+regexp}}
| O(m)
| Ω(n/m) at best,<br/> O(mn) at worst
|
|-
| |||