Analysis of Boyer-Moore

COMPUTE-LAST-OCCURRENCE-FUNCTION is tex2html_wrap_inline388

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

so BOYER-MOORE-MATCHER is tex2html_wrap_inline392

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

next up previous
Next: STRING MATCHING WITH FINITE Up: BOYER-MOORE Previous: Analysis of Compute-Good-Suffix-Function