  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 known as position weight matrices or
uncertain sequences, naturally arise in many contexts. In this article, we
study the problem of weighted string matching with a special focus on
average-case analysis. Given a weighted pattern string $x$ of length $m$, a
text string $y$ of length $n>m$, and a cumulative weight threshold $1/z$,
defined as the minimal probability of occurrence of factors in a weighted
string, we present an algorithm requiring average-case search time $o(n)$ for
pattern matching for weight ratio $\frac{z}{m} < \min\{\frac{1}{\log
z},\frac{\log \sigma}{\log z (\log m + \log \log \sigma)}\}$. For a pattern
string $x$ of length $m$, a weighted text string $y$ of length $n>m$, and a
cumulative weight threshold $1/z$, we present an algorithm requiring
average-case search time $o(\sigma n)$ for the same weight ratio. The
importance of these results lies on the fact that these algorithms work in
average-case sublinear search time in the size of the text, and in linear
preprocessing time and space in the size of the pattern, for these ratios.
