Editing String-searching algorithm (section)

==== 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
| 
| 
| 
|}