String-searching algorithm: Difference between revisions

Revision as of 18:42, 27 January 2024

Latest revision as of 17:09, 26 July 2025

(20 intermediate revisions by 15 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 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 211 ⟶ 260:

*[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}}