String-searching algorithm: Difference between revisions

Revision as of 20:27, 19 January 2023

Revision as of 02:14, 3 February 2023

Line 95:

| O(1)

|-

! Backward Non-Deterministic [[DirectedSuffix acyclic word graphautomaton|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