Analysis of Boyer-Moore

COMPUTE-LAST-OCCURRENCE-FUNCTION is $O(m+\vert\Sigma\vert)$

COMPUTE-GOOD-SUFFIX-FUNCTION is O(m)

so BOYER-MOORE-MATCHER is $O((n-m+1)m + \vert\Sigma\vert)$

So, theoretically no better than NAIVE (actually a little worse), but in practice it seems to do better.