[prev] 24 [next]

Boyer-Moore Algorithm (cont)

l … last occurrence L[T[i]] of character T[i]

Why i = i + m - min(j,1+l)?

  • Case 1: 1+l ≤ j    ⇒ i = i+m-(1+l)

    [Diagram:Pic/boyer-moore-case2.png]

  • Case 2: j ≤ l    ⇒ i = i+m-j

    [Diagram:Pic/boyer-moore-case1.png]