28
Exercise 1: Boyer-Moore algorithm
For the alphabet Σ = {
a,b,c,d
}
compute last-occurrence function
L
for pattern
P
=
abacab
trace Boyer-More on
P
and text
T
=
abacaabadcabacabaabb
how many comparisons are needed?
c
a
b
c
d
L(c)
4
5
3
-1
13 comparisons in total