[prev] 27 [next]

Boyer-Moore Algorithm (cont)

Analysis of Boyer-Moore algorithm:
  • Runs in O(nm+s) time
    • m … length of pattern    n … length of text    s … size of alphabet
  • Example of worst case:
    • T = aaa … a
    • P = baaa
  • Worst case may occur in images and DNA sequences but unlikely in English texts
    ⇒ Boyer-Moore significantly faster than naive matching on English text