Algorithms for String matching
Marc Gou · 2014
A string matching algorithm aims to nd one or several occurrences of a string within another. The algorithm returns the position of the rst character of the desired substring in the text. There are many dierent solutions for this problem, this article presents the four best-known string matching algorithms: Naive, Knuth-Morris-Pratt, Boyer-Moore and Rabin-Karp. The results show that Boyce-Moore is the most eective algorithm to solve the string matching problem in usual cases, and Rabin-Karp is a good alternative for some specic cases, for example when the pattern and the alphabet are very small.