Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Home > Boyer-Moore string search algorithm
Boyer-Moore algorithm is the fastest known string searching algorithm, at least in its best case. For a text of length n and a fixed pattern of length m the best performance of the algorithm is n/m and the worst case is n*m. The algorithm is very widely used in software engineering. The notable feature of the algorithm, apparent from its running time formula, is that the longer the pattern we are looking for, the faster the algorithm will be usually able to find it.The algorithm works by precomputing two sets of jump tables. The first table () gives the next offset at which a match could possibly occur given the last (nonmatching) character encountered while comparing the pattern with the text; the second () gives a similar offset based on the number of characters that matched correctly. When a mismatch occurs, the largest of these two values is used to skip ahead to the next position where a match could potentially occur.
External link
Algorithms on strings
Read more »