Discussion:
Boyer Moore
(too old to reply)
David Kaufman
2011-08-09 23:48:58 UTC
Permalink
Hi,
I just wanted to make sure I understand Boyer Moore Algorithm and
comparison count correctly. In the online notes module-8, slide 29/39,
we are searching for the pattern moore in the string boyermoore. it
claims we do 7 comparisons. By my count, it seems we do 6 comparisons.
Is this a mistake, or am I misunderstanding the comparison(check) count?
Thanks
David
Daniel S. Roche
2011-08-10 03:10:20 UTC
Permalink
Post by David Kaufman
I just wanted to make sure I understand Boyer Moore Algorithm and
comparison count correctly. In the online notes module-8, slide 29/39,
we are searching for the pattern moore in the string boyermoore. it
claims we do 7 comparisons. By my count, it seems we do 6 comparisons.
Is this a mistake, or am I misunderstanding the comparison(check) count?
No, you are correct, it is 6 comparisons. I noticed this while lecturing
but forgot to post an errata; sorry.

-Dan Roche
CS 240 Instructor, Section 003
David Kaufman
2011-08-10 03:45:11 UTC
Permalink
Post by Daniel S. Roche
Post by David Kaufman
I just wanted to make sure I understand Boyer Moore Algorithm and
comparison count correctly. In the online notes module-8, slide 29/39,
we are searching for the pattern moore in the string boyermoore. it
claims we do 7 comparisons. By my count, it seems we do 6 comparisons.
Is this a mistake, or am I misunderstanding the comparison(check) count?
No, you are correct, it is 6 comparisons. I noticed this while lecturing
but forgot to post an errata; sorry.
-Dan Roche
CS 240 Instructor, Section 003
So just to clarify then: Whenever you have implied (noted by brackets)
characters, in Boyer Moore or KMP algorithm (based on or Last
Occurrence/Good Suffix/Failure Array) , we don't need to count those
towards out comparisons. Is this correct?

Loading...