String-searching algorithm: Difference between revisions

Revision as of 11:10, 10 August 2016

Revision as of 07:57, 11 August 2016

Line 1:

In [[computer science]], '''string searching algorithms''', sometimes called '''string matching algorithms''', are an important class of [[String_String (computer_sciencecomputer science)#String_processing_algorithmsString processing algorithms|string algorithms]] that try to find a place where one or several [[string (computer science)|strings]] (also called [[pattern]]s) are found within a larger string or text.

Let Σ be an [[Alphabet (computer science)|alphabet]] ([[finite set]]). Formally, both the pattern and searched text are vectors of elements of Σ. The Σ may be a usual human alphabet (for example, the letters A through Z in the Latin alphabet). Other applications may use ''binary alphabet'' (Σ = {0,1}) or ''DNA alphabet'' (Σ = {A,C,G,T}) in [[bioinformatics]].

Line 84:

|}

Another one classifies the algorithms by their matching strategy :<ref>{{Literatur|Autor=Gonzalo Navarro, Mathieu Raffinot|Titel=Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences|Jahr=2008|ISBN=0-521-03993-2}}</ref>:

* Match the prefix first (Knuth-Morris-Pratt, Shift-And, Aho-Corasick)

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