  We propose a framework for the exact probabilistic analysis of window-based
pattern matching algorithms, such as Boyer-Moore, Horspool, Backward DAWG
Matching, Backward Oracle Matching, and more. In particular, we show how to
efficiently obtain the distribution of such an algorithm's running time cost
for any given pattern in a random text model, which can be quite general, from
simple uniform models to higher-order Markov models or hidden Markov models
(HMMs). Furthermore, we provide a technique to compute the exact distribution
of \emph{differences} in running time cost of two algorithms. In contrast to
previous work, our approach is neither limited to simple text models, nor to
asymptotic statements, nor to moment computations such as expectation and
variance. Methodically, we use extensions of finite automata which we call
deterministic arithmetic automata (DAAs) and probabilistic arithmetic automata
(PAAs) [13]. To our knowledge, this is the first time that substring- or
suffix-based pattern matching algorithms are analyzed exactly. Experimentally,
we compare Horspool's algorithm, Backward DAWG Matching, and Backward Oracle
Matching on prototypical patterns of short length and provide statistics on the
size of minimal DAAs for these computations.
