String-searching algorithm: Difference between revisions

Revision as of 17:53, 15 January 2016

Revision as of 00:20, 9 April 2016

Line 15:

! Algorithm

! Preprocessing time

! Matching time¹{{ref|Asymptotic times}}

|-

! Naïve string search algorithm

Line 41:

| O(mn)

|}

^:1.{{note|Asymptotic times}}Asymptotic times are expressed using [[Big O notation|O, Ω, and Θ notation]].

The '''[[Boyer–Moore string search algorithm]]''' has been the standard benchmark for the practical string search literature.<ref name=":0">{{cite journal |last=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 }}</ref>