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>M^2$, on all alphabet sizes, is needed.