String-searching algorithm: Difference between revisions

Revision as of 07:50, 22 March 2022

Revision as of 07:58, 22 March 2022

Line 90:

| Θ(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}}</ref>{{ref|glibclibc}}

| Θ(m)

| O(n+m)

Line 106:

|}

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

:2.{{note|glibclibc}}Used into [[glibc]]'s implementation ofimplement 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}}</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}}</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 languages]].