[prev] 28 [next]

Exercise 1: Boyer-Moore algorithm

For the alphabet Σ = {a,b,c,d}

  1. compute last-occurrence function L for pattern P = abacab
  2. trace Boyer-More on P and text T = abacaabadcabacabaabb
    • how many comparisons are needed?


cabcd
L(c)453-1

[Diagram:Pics/tries/boyer-moore-example.png]


13 comparisons in total