[prev] 22 [next]

Boyer-Moore Algorithm (cont)

Boyer-Moore algorithm preprocesses pattern P and alphabet Σ to build
  • last-occurrence function L
    • L maps Σ to integers such that L(c) is defined as
      • the largest index i such that P[i]=c, or
      • -1 if no such index exists
Example: Σ = {a,b,c,d}, P = acab

cabcd
L(c)231-1
  • L can be represented by an array indexed by the numeric codes of the characters
  • L can be computed in O(m+s) time   (m … length of pattern, s … size of Σ)