A Fast Heuristic for Exact String Matching

Given a pattern string $P$ of length $n$ consisting of $δ$ distinct characters and a query string $T$ of length $m$, where the characters of $P$ and $T$ are drawn from an alphabet $Σ$ of size $Δ$, the {\em exact string matching} problem consists of finding all occurrences of $P$ in $T$. For this problem, we present a randomized heuristic that in $O(nδ)$ time preprocesses $P$ to identify $sparse(P)$, a rarely occurring substring of $P$, and then use it to find all occurrences of $P$ in $T$ efficiently. This heuristic has an expected search time of $O( \frac{m}{min(|sparse(P)|, Δ)})$, where $|sparse(P)|$ is at least $δ$. We also show that for a pattern string $P$ whose characters are chosen uniformly at random from an alphabet of size $Δ$, $E[|sparse(P)|]$ is $Ω(Δlog (\frac{2Δ}{2Δ-δ}))$.