| FazBrowse Wikipedia Viewer | Main Page | | |
| Viewing: https://en.wikipedia.org/wiki/String-searching_algorithm |
A string-searching algorithm, sometimes called string-matching algorithm, is an algorithm that searches a body of text for portions that match by pattern.
A basic example of string searching is when the pattern and the searched text are arrays of elements of an 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.
In practice, the method of feasible string-search algorithm may be affected by the string encoding. In particular, if a variable-width encoding is in use, then it may be slower to find the Nth character, perhaps requiring time proportional to N. This may significantly slow some search algorithms. One of many possible solutions is to search for the sequence of code units instead, but doing so may produce false matches unless the encoding is specifically designed to avoid it.Θ(n) time, and all
The Boyer–Moore string-search algorithm has been the standard benchmark for the practical string-search literature.
In the following compilation, M is the length of the longest pattern, m their total length, n the length of the searchable text, o the number of occurrences.
| Algorithm | Extension of | Preprocessing time | Matching time | Space |
|---|---|---|---|---|
| Aho–Corasick | Knuth–Morris–Pratt | Θ(m) | Θ(n + o) | Θ(m) |
| Commentz-Walter | Boyer-Moore | Θ(m) | Θ(M * n) worst case sublinear in average |
Θ(m) |
| Set-BOM | Backward Oracle Matching |
Naturally, the patterns can not be enumerated finitely in this case. They are represented usually by a regular grammar or regular expression.
Other classification approaches are possible. One of the most common uses preprocessing as main criteria.
| Text not preprocessed | Text preprocessed | |
|---|---|---|
| Patterns not preprocessed | Elementary algorithms | Index methods |
| Patterns preprocessed | Constructed search engines | Signature methods |
Another one classifies the algorithms by their matching strategy:
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.
String searching with don't careseditIn 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
| View original on Wikipedia | Back | FazBrowse Home |