Premium
The Boyer–Moore–Horspool heuristic with Markovian input
Author(s) -
Smythe R. T.
Publication year - 2001
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/1098-2418(200103)18:2<153::aid-rsa1003>3.0.co;2-o
Subject(s) - markov chain , probabilistic logic , markov process , struct , mathematics , heuristic , algorithm , normalization (sociology) , discrete mathematics , independent and identically distributed random variables , sequence (biology) , combinatorics , computer science , random variable , statistics , mathematical optimization , sociology , biology , anthropology , genetics , programming language
The Boyer–Moore–Horspool string‐matching heuristic is an algorithm for locating occurrences of a fixed pattern in a random text. Under the assumption that the text is an independently and identically distributed sequence of characters, the probabilistic behavior of this algorithm was investigated by Mahmoud, Smythe, and Régnier [Random Struct Alg 10 (1997), 169–186]. Here, we obtain similar results under the assumption that the text is generated by an irreducible Markov chain. A natural Markov renewal process structure is exploited to obtain the asymptotic behavior of the number of comparisons. Under suitable normalization, it is shown that a central limit theorem holds for the number of comparisons. The analysis is completely probabilistic and does not use the shift generating function. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 153–163, 2001