Fast Average-Case Pattern Matching on Weighted Sequences

Carl Barton, Chang Liu, Solon P. Pissis

A weighted string over an alphabet of size $\sigma$ is a string in which a set of letters may occur at each position with respective occurrence probabilities. Weighted strings, also kno…