String-searching algorithm: Difference between revisions

Revision as of 17:16, 7 October 2023

Latest revision as of 17:09, 26 July 2025

(28 intermediate revisions by 20 users not shown)

Line 1:

{{short description|SearchesSearching for patterns withinin stringstext}}

In [[computer science]],A '''string-searching algorithmsalgorithm''', sometimes called '''string-matching algorithmsalgorithm''', areis an important class of [[string algorithmsalgorithm]] that try to findsearches a placebody where one or severalof [[string (computer science)|stringstext]] (alsofor calledportions patterns)that arematch foundby within a larger string or textpattern.

A basic example of string searching is when the pattern and the searched text are [[Array data structure|arrays]] of elements of an [[Alphabet (computer science)|alphabet]] ([[finite set]]) Σ. Σ may be a human language alphabet, for example, the letters ''A'' through ''Z'' and other applications may use a ''binary alphabet'' (Σ = {0,1}) or a ''DNA alphabet'' (Σ = {A,C,G,T}) in [[bioinformatics]].

Line 72:

! Naïve algorithm

| none

| Θ(n+m) in average,<br/> O(mn)

| none

|-

! Automaton-based matching

| Θ(km)

| Θ(n)

| Θ(km)

|-

! [[Rabin–Karp algorithm|Rabin–Karp]]

Line 87 ⟶ 92:

! [[Boyer–Moore string-search algorithm|Boyer–Moore]]

| Θ(m + k)

| ΩO(n/m) at best,<br/> O(mn) at worst

| Θ(k)

|-

Line 107 ⟶ 112:

: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 languageslanguage]]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 |url=https://semanticscholar.org/paper/d9912ea262986794e29e3f15e5f8930d42f2ced4 |access-date=2019-11-29 |archive-date=2022-05-10 |archive-url=https://web.archive.org/web/20220510030246/https://www.semanticscholar.org/paper/Fast-string-searching-Hume-Sunday/d9912ea262986794e29e3f15e5f8930d42f2ced4 |url-status=live }}</ref>

==== Algorithms using a finite set of patterns ====

Line 159 ⟶ 164:

! Patterns preprocessed

| Constructed search engines

| Signature methods :<ref>{{citation |surname1last1=RiadLitwin Mokadem|surname2first1=Witold Litwin|last2=Mokadem http|first2=Riad |last3=Rigaux |first3=Philippe |last4=Schwarz |first4=Thomas |url=https://www.csevldb.scu.eduorg/~tschwarzconf/Papers2007/vldb07_finalpapers/research/p207-litwin.pdf |title=Fast nGramBasednGram-Based String Search Over Data Encoded Using Algebraic Signatures |year=2007 |publisher=33rd [[International Conference on Very Large Data Bases (VLDB)]]}}</ref>

|}

Line 168 ⟶ 173:

* Match the suffix first (Boyer–Moore and variants, Commentz-Walter)

* Match the best factor first (BNDM, BOM, Set-BOM)

* Other strategy (Naïve, Rabin–Karp, Vectorized)

===Real-time string matching===

In real-time string matching, one requires the matcher to output a response after reading each character of the text, that indicates

whether this is the last character of a match. The response has to be given within constant time.

The requirement regarding preprocessing vary: O(''m'') preprocessing may be allowed after the pattern is read (but before the reading of

the text), or a stricter requirement may be posed according to which the matcher has to also pause for at most a constant time after reading any character of the pattern (including the last).

For the more lenient version, if one does not mind that the preprocessing time and memory requirement dependend on the size of the alphabet, a real-time solution is provided by

automaton matching.

[[Zvi Galil]] developed a method to turn certain algorithms into real-time algorithms, and applied it to produce a variant of the KMP

matcher that runs in real time under the strict requirement.<ref>{{Cite journal

| last = Galil

| first = Zvi

| title = String matching in real time

| journal = Journal of the ACM

| volume = 28

| issue = 1

| pages = 134–149

| year = 1981

| doi = 10.1145/322234.322244

| pmid =

| url =

}}</ref>

==String searching with don't cares==

In this version of the string searching problem, there is a special symbol, ø (read: don't care), which can match any other symbol (including another ø).

Don't care symbols can appear either in the pattern or in the text. In 2002, an algorithm for this problem that runs in <math>O(n\log m)</math> time has been

given by [[Richard Cole]] and [[Ramesh Hariharan]], improving on a solution from 1973 by [[Michael J. Fischer|Fischer]] and [[Michael S. Paterson|Paterson]]

that has complexity <math>O(n\log m\log k)</math>, where ''k'' is the size of the alphabet.<ref>{{Cite conference

| last1 = Cole

| first1 = Richard

| last2 = Hariharan

| first2 = Ramesh

| title = Verifying candidate matches in sparse and wildcard matching

| book-title = Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

| editor =

| publisher =

| ___location =

| pages = 592–601

| year = 2002

| url =

| doi =

}}</ref> Another algorithm, claimed simpler, has been proposed by [[Peter Clifford (mathematician)|Clifford]] and [[Raphaël Clifford|Clifford]].<ref>{{cite journal |last1=Clifford |first1=Peter |last2=Clifford |first2=Raphaël |title=Simple deterministic wildcard matching |journal=Information Processing Letters |date=January 2007 |volume=101 |issue=2 |pages=53–54 |doi=10.1016/j.ipl.2006.08.002}}</ref>

==See also==

Line 176 ⟶ 224:

*[[Compressed pattern matching]]

*[[Matching wildcards]]

*[[Approximate string matching]]

*[[Full-text search]]

Line 208 ⟶ 257:

*[http://stringsandchars.amygdalum.net/ StringsAndChars] – Implementations of many String-Matching-Algorithms (for single and multiple patterns) in Java

*[http://www-igm.univ-mlv.fr/~lecroq/string/index.html Exact String Matching Algorithms] — Animation in Java, Detailed description and C implementation of many algorithms.

*[http://www.cs.ucr.edu/~stelo/cpm/cpm04/35_Navarro.pdf (PDF) Improved Single and Multiple Approximate String Matching] {{Webarchive|url=https://web.archive.org/web/20170311221134/http://www.cs.ucr.edu/~stelo/cpm/cpm04/35_Navarro.pdf |date=2017-03-11 }}

*[https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2647288/ Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features]

*[https://www.codeproject.com/Articles/5282980/Fastest-Fulltext-Vector-Scalar-Exact-Searcher NyoTengu – high-performance pattern matching algorithm in C] – Implementations of Vector and Scalar String-Matching-Algorithms in C

*[https://arxiv.org/html/2502.20338v3 Nathaniel K. Brown, et al.: "KeBaB: k-mer based breaking for finding long MEMs", arXiv:2502.20338v3 (09 Jun 2025).]

{{strings}}