Commentz–Walter algorithm

Commentz–Walter algorithm: The Commentz-Walter algorithm is a string searching algorithm invented by Beate Commentz-Walter. Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho-Corasick with the fast matching of the Boyer–Moore string search algorithm.

GNU grep implements a string matching algorithm very similar to Commentz-Walter^[1].

References

^ http://git.savannah.gnu.org/cgit/grep.git/tree/src/kwset.c

External links

http://www.hs-albsig.de/studium/wirtschaftsinformatik/Documents/commentzwalterextab.pdf

Categories:
Algorithms on strings
Search algorithms
Algorithm stubs

Игры ⚽ Нужна курсовая?

String searching algorithm — String searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. Let Σ be… … Wikipedia
Boyer–Moore string search algorithm — The Boyer–Moore string search algorithm is a particularly efficient string searching algorithm, and it has been the standard benchmark for the practical string search literature. [Hume and Sunday (1991) [Fast String Searching] SOFTWARE PRACTICE… … Wikipedia

Academic Dictionaries and Encyclopedias