Premium
Average case analysis of the Boyer‐Moore algorithm
Author(s) -
Tsai TsungHsi
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20111
Subject(s) - struct , limiting , limit (mathematics) , algorithm , mathematics , variance (accounting) , constant (computer programming) , computer science , combinatorics , discrete mathematics , mechanical engineering , mathematical analysis , accounting , engineering , business , programming language
Limit theorems (including a Berry‐Esseen bound) are derived for the number of comparisons taken by the Boyer‐Moore algorithm for finding the occurrences of a given pattern in a random text. Previously, only special variants of this algorithm have been analyzed. We also propose a means of computing the limiting constants for the mean and the variance. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006.