Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata

Tobias Marschall, Sven Rahmann

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 Matc…