Algorithms and Data Structures

50 Algos In 50 Weeks: Implementing Boyer–Moore string search algorithm

July 12, 2012 · 7:00 PM
Pivotal Labs

In computer science, the Boyer–Moore string search algorithm is an efficient string searching algorithm that is the standard benchmark for practical string search literature.[1] It was developed by Robert S. Boyer and J Strother Moore in 1977.[2] The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well-suited for applications in which the text does not persist across multiple searches. The Boyer-Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string algorithms. In general, the algorithm runs faster as the pattern length increases.

Join or login to comment.

Vikas Taneja

Thanks! I am grad you liked it.
Yeah, it is not covering the Bad Character rule, but is still better than brute force method in majority of cases. Also, when I started to understand the algorithm, I was not very much clear. So, when I understood it, I thought of blogging it to help others get started. :)

0 · July 13
Benjamin

Nice post, but you only cover the Bad Character Rule. Still, I liked the simple explanation :)

0 · July 13
Vikas Taneja

Yeah, this algo is pretty sweet. I have written a blog on it a while back, if anyone is interested in reading it:
http://algorithmproblemoftheday...

0 · July 13
Sajit

Thanks Andy, Complex Algo made simple

0 · July 13
Zach Jablons

There was really no preparation of the material by the organizers beforehand, although it was still informative.

0 · July 13
max gribov

Was pretty awesome, despite the slight tension headache i got :)
Am wondering, what if i loop through entire text string, recording the index position of the first letter in my pattern. Then, go back to each of those indeces +1 and record them if i find my second char from the pattern - repeat till done.
That would give O(m*n) as well, no?

0 · July 12
Benjamin

I might be able to organize one myself, I just need to find a suitable topic :)

0 · July 12
Jesse C

I think we've got some organizers who stepped up to help carry through in his absence.

0 · July 12
Darren Kong

Although unless things have changed, Andy's going to be gone for ~4 months though after this meetup :(.

0 · July 12
Benjamin

Nope, you can come next time :)

0 · July 12
Sidney San Martín

I can't come this week (helping set up HOPE!)... This isn't the last one, right?

0 · July 12
Benjamin

Tom, there is plenty of people that RSVP yes that don't show up. Just come, we'll find you a spot :)

Vikas: Too bad, just drop by if you happen to be in New York a Thursday ;)

0 · July 12
Vikas Taneja

The problem is that I'm in West coast...seems like there is no option I can attend from here.

0 · July 11
Tom

no spots left?

0 · July 11
Benjamin

Sorry Vikas but it is not an online meetup, there's no recording of the session, you have to show up to enjoy it :)

0 · July 11
Vikas Taneja

Is it an online meetup too? If not, can we have video recording of the session available too, of course after the meeting?

0 · July 11