Editing String-searching algorithm (section)

=== Classification by a number of patterns ===
The various [[algorithm]]s can be classified by the number of patterns each uses.

==== Single-pattern algorithms ====
In the following compilation, ''m'' is the length of the pattern, ''n'' the length of the searchable text, and ''k'' = |Σ| is the size of the alphabet.
{| class="wikitable"
|-
! Algorithm
! Preprocessing time
! Matching time{{ref|Asymptotic times}}
! Space
|-
! Naïve algorithm
| none
| Θ(n+m) in average,<br/> O(mn)
| none
|-
! [[Rabin–Karp algorithm|Rabin–Karp]]
| Θ(m)
| Θ(n) in average,<br/> O(mn) at worst
| O(1)
|-
! [[Knuth–Morris–Pratt algorithm|Knuth–Morris–Pratt]]
| Θ(m)
| Θ(n)
| Θ(m)
|-
! [[Boyer–Moore string-search algorithm|Boyer–Moore]]
| Θ(m + k)
| Ω(n/m) at best,<br/> O(mn) at worst
| Θ(k)
|-
! [[Two-way string-matching algorithm|Two-way algorithm]]<ref>{{cite journal |last1=Crochemore |first1=Maxime |last2=Perrin |first2=Dominique |title=Two-way string-matching |journal=Journal of the ACM |date=1 July 1991 |volume=38 |issue=3 |pages=650–674 |doi=10.1145/116825.116845 |s2cid=15055316 |url=http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf |access-date=5 April 2019 |archive-date=24 November 2021 |archive-url=https://web.archive.org/web/20211124025145/http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf |url-status=live }}</ref>{{ref|libc}}
| Θ(m)
| O(n)
| O(log(m))
|-
! Backward Non-Deterministic [[Suffix automaton|DAWG]] Matching (BNDM)<ref>{{cite book |last1=Navarro |first1=Gonzalo |last2=Raffinot |first2=Mathieu |title=Combinatorial Pattern Matching |chapter=A bit-parallel approach to suffix automata: Fast extended string matching |date=1998 |volume=1448 |pages=14–33 |doi=10.1007/bfb0030778 |chapter-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
| 
|-
! Backward Oracle Matching (BOM)<ref>{{cite book |last1=Fan |first1=H. |last2=Yao |first2=N. |last3=Ma |first3=H. |title=2009 Fourth International Conference on Internet Computing for Science and Engineering |chapter=Fast Variants of the Backward-Oracle-Marching Algorithm |date=December 2009 |pages=56–59 |doi=10.1109/ICICSE.2009.53 |chapter-url=https://pdfs.semanticscholar.org/8d81/94c293f8a81394ba545d09bd6ec711ad4c17.pdf |isbn=978-1-4244-6754-9 |s2cid=6073627 |access-date=2019-11-22 |archive-date=2022-05-10 |archive-url=https://web.archive.org/web/20220510030242/https://www.semanticscholar.org/paper/Efficient-Variants-of-the-Backward-Oracle-Matching-Faro-Lecroq/d24e4bad432e5b88b4fb752ba868e3d3e609a2c4?p2df |url-status=live }}</ref>
| O(m)
| O(mn)
| 
|}
:1.{{note|Asymptotic times}}Asymptotic times are expressed using [[Big O notation|O, Ω, and Θ notation]].
:2.{{note|libc}}Used to implement the ''memmem'' and [[C string handling#Functions|''strstr'']] search functions in the [[glibc]]<ref>{{cite web |title=glibc/string/str-two-way.h |url=https://code.woboq.org/userspace/glibc/string/str-two-way.h.html |access-date=2022-03-22 |archive-date=2020-09-20 |archive-url=https://web.archive.org/web/20200920180414/https://code.woboq.org/userspace/glibc/string/str-two-way.h.html |url-status=live }}</ref> and [[musl]]<ref>{{cite web |title=musl/src/string/memmem.c |url=http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |access-date=23 November 2019 |archive-date=1 October 2020 |archive-url=https://web.archive.org/web/20201001184748/http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |url-status=live }}</ref> [[C standard libraries]].
:3.{{note|fuzzy+regexp}}Can be extended to handle [[approximate string matching]] and (potentially-infinite) sets of patterns represented as [[regular language]]s.{{Citation needed|date=March 2022|reason=No reference found for the 2-way algorithm}}

The '''[[Boyer–Moore string-search algorithm]]''' has been the standard benchmark for the practical string-search literature.<ref name=":0">{{cite journal |last1=Hume |last2=Sunday |year=1991 |title=Fast String Searching |journal=Software: Practice and Experience |volume=21 |issue=11 |pages=1221–1248 |doi=10.1002/spe.4380211105 |s2cid=5902579 }}</ref>

==== Algorithms using a finite set of patterns ====
In the following compilation, ''M'' is the length of the longest pattern, ''m'' their total length, ''n'' the length of the searchable text, ''o'' the number of occurrences.

{| class="wikitable"
|-
! Algorithm
! Extension of
! Preprocessing time
! Matching time{{ref|Asymptotic times}}
! Space
|-
! [[Aho–Corasick algorithm|Aho–Corasick]]
| [[Knuth–Morris–Pratt algorithm|Knuth–Morris–Pratt]]
| Θ(m)
| Θ(n + o)
| Θ(m)
|-
! [[Commentz-Walter algorithm|Commentz-Walter]]
| [[Boyer–Moore string-search algorithm|Boyer-Moore]]
| Θ(m)
| Θ(M * n) worst case <br/> sublinear in average<ref name="Commentz-Walter"/>
| Θ(m)
|-
! Set-BOM
| Backward Oracle Matching
| 
| 
| 
|}

==== Algorithms using an infinite number of patterns ====
Naturally, the patterns can not be enumerated finitely in this case. They are represented usually by a [[regular grammar]] or [[regular expression]].