Average complexity of backward q-gram string matching algorithms

Many efficient string matching algorithms make use of q-grams and process the text in windows which are read backward. In this paper we provide a framework for analyzing the average case complexity of these algorithms taking into account the statistical dependencies between overlapping q-grams. We apply this to the q-gram Boyer–Moore–Horspool algorithm adapted to various string matching problems and show that the algorithm is optimal on average.

► We study the average case complexity of string matching algorithms that use q-grams.
► We take into account the statistical dependencies of overlapping q-grams.
► We show that q-gram Boyer–Moore–Horspool style algorithms are average optimal.