Details

Autor(en) / Beteiligte

• Tsai, Tsung-Hsi

Titel

Average case analysis of the Boyer-Moore algorithm

Ist Teil von

• Random structures & algorithms, 2006-07, Vol.28 (4), p.481-498

Ort / Verlag

Hoboken: Wiley Subscription Services, Inc., A Wiley Company

Erscheinungsjahr

2006

Link zum Volltext

Quelle

Wiley Online Library All Journals

Beschreibungen/Notizen

• 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.