Is the running time of Boyer-Moore linear?
Here is a true sublinear string matching algorithm, on all alphabet sizes, which answers the question Kaveh posted. My question was: Is Boyer-Moore actually linear on small alphabets?

The log base below is $|\Sigma|$, and (ceiling of) $logM$ (often just one) is implied.

Preprocess the Pattern into a lookup table, with $M-logM+1$ keys, each key having size $logM$, and with associated key positions in the Pattern. Converting sequences of $logM$ letters into array indices is the only tricky part. The table size is $|\Sigma|$ raised to ceiling of $logM$, for easy indexing.  Each bucket is a short, possibly empty, list of key positions.  Run time: $O( MlogM )$.

Main: Skip through Text positions $k$ by $(M - logM + 1)$, constructing a $logM$ sized search key at Text positions $k$ thru $k + logM -1$. Look up the search key in the table. If found, naively attempt to match the Pattern at Text[$k$ - key position].  The naive attempt almost certainly fails in $logM$ comparisons. The only tricky part is that a key may occur in multiple Pattern positions.  The expected number of test positions is $O(1)$.  Expected run time: $O( (N/M)logM )$.

Post: Garbage collect the preprocessing space, $O(MlogM)$.

A proof that Main is optimal for $N&gt;M^2$, on all alphabet sizes, is needed.