Average case analysis of the Boyer‐Moore algorithm | Zendy

Tsai TsungHsi | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research