Content deleted Content added
→External links: removed dead link, added link to multi string implementations |
→Basic classification: added some more algorithms and a reference to a book containing very many algorithms (even for multiple and wildcard patterns) |
||
Line 6:
== Basic classification ==
The various [[algorithm]]s can be classified by the number of patterns each uses
* Match the prefix first (Knuth-Morris-Pratt, Bitap)
* Match the suffix first (Boyer-Moore and variants)
* Match the best factor first (BNDM, BOM)
* Other strategy (Naive, Rabin-Karp)
=== Single pattern algorithms ===
Line 44 ⟶ 48:
| Θ(m)
| O(n+m)
|-
! BNDM (Backward Non-Deterministic Dawg Matching)
| O(m)
| O(n)
|-
! BOM (Backward Oracle Matching)
| O(m)
| O(n)
|}
:1.{{note|Asymptotic times}}Asymptotic times are expressed using [[Big O notation|O, Ω, and Θ notation]].
Line 50 ⟶ 62:
=== Algorithms using a finite set of patterns ===
* [[Aho–Corasick string matching algorithm]] (extension of Knuth-Morris-Pratt)
* [[Commentz-Walter algorithm]] (extension of Boyer-Moore)
* Set-BOM (extension of Backward Oracle Matching)
* [[Rabin–Karp string search algorithm]]
| |||