## 1 Introduction  
The basic pattern matching problem is to find all occurrences of a _pattern_ string in a (long) _text_ string, with few character accesses, where a _character access_ is the act of retrieving one character of the input string from memory. For many pattern matching algorithms, this is equivalent to speaking of character _comparisons_, as every accessed character is immediately compared to a character in the pattern. However, for some algorithms (e.g., the Knuth-Morris-Pratt algorithm [2]), each character access triggers a table lookup rather than a comparison. Thus, we discuss character accesses rather than character comparisons in the remainder of this article. Let \(n\) be the text length and \(m\) be the pattern length. The well-known Knuth-Morris-Pratt algorithm [2] reads each text character exactly once from left to right and hence needs exactly \(n\) character accesses for any text of length \(n\), after preprocessing the pattern in \(\Theta(m)\) time. In contrast, the Boyer-Moore [3], Horspool [4], Sunday [5], Backward DAWG Matching (BDM, [6]) and Backward Oracle Matching (BOM, [7]) algorithms move a length-\(m\) search window across the text and first compare its _last_ character to the last character of the pattern. This often allows to move the search window by more than one position (at best, by \(m\) positions if the last window character does not occur in the pattern at all), for a best case of \(n/m\), but a worst case of \(mn\) character accesses. The worst case can often be improved to \(\Theta(m+n)\), but this makes the code more complicated and seldom provides a speed-up in practice. For practical pattern matching applications, the most important algorithms are Horspool, BDM (often implemented as Backward Nondeterministic DAWG Matching, BNDM, via a non-deterministic automaton that is simulated in a bit-parallel fashion), and BOM, depending on alphabet size, text length and pattern length; see [8] for an experimental map. A question that has apparently so far not been investigated is about the exact probability distribution of the number of required character accesses \(X_{n}^{p}\) when matching a given pattern \(p\) against a random text of finite length \(n\) (non-asymptotic case), even though related questions have been answered in the literature. For example, [9; 10] analyze the expected value of \(X_{n}^{p}\) for the Horspool algorithm. In [11] it is further shown that for the Horspool algorithm, \(X_{n}^{p}\) is asymptotically normally distributed for random texts with independent and identically distributed (i.i.d.) characters, and [12] extends this result to Markovian text models. In [13], a method to compute mean and variance of these distributions is given. In contrast to these results that are special to the Horspool algorithm, we use a general framework called _probabilistic arithmetic automata_ (PAAs), introduced at CPM'08 [1], to compute the exact distribution of \(X_{n}^{p}\) for any window-based pattern matching algorithm. In [1], PAAs were introduced in order to compute the distribution of occurrence counts of patterns, a purpose for which multiple other researchers have also proposed to combine finite automata with probabilistic text models [14; 15; 16; 17]. Especially the early approach of [PERSON] _et al_. [14] has shown how to derive generating functions and perform asymptotic analysis of occurrence distributions. Here, we show that a similar idea can be applied to the analysis of pattern matching algorithms by constructing an automaton that encodes the behavior of such an algorithm and then combining it with a text model. The PAA framework allows doing this in a natural way, which further highlights its utility. The random text model can be quite general, from simple i.i.d. uniform models to high-order Markov models or HMMs. The approach is applied to the following pattern matching algorithms in the non-asymptotic regime (short patterns, medium-length texts): Horspool, B(N)DM, BOM.