|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Fast Generic Sequence Matching Algorithm | | David R. Musser
; Gor V. Nishanov
; | | Date: |
1 Oct 2008 | | Abstract: | A string matching -- and more generally, sequence matching -- algorithm is
presented that has a linear worst-case computing time bound, a low worst-case
bound on the number of comparisons (2n), and sublinear average-case behavior
that is better than that of the fastest versions of the Boyer-Moore algorithm.
The algorithm retains its efficiency advantages in a wide variety of sequence
matching problems of practical interest, including traditional string matching;
large-alphabet problems (as in Unicode strings); and small-alphabet,
long-pattern problems (as in DNA searches). Since it is expressed as a generic
algorithm for searching in sequences over an arbitrary type T, it is well
suited for use in generic software libraries such as the C++ Standard Template
Library. The algorithm was obtained by adding to the Knuth-Morris-Pratt
algorithm one of the pattern-shifting techniques from the Boyer-Moore
algorithm, with provision for use of hashing in this technique. In situations
in which a hash function or random access to the sequences is not available,
the algorithm falls back to an optimized version of the Knuth-Morris-Pratt
algorithm. | | Source: | arXiv, 0810.0264 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER