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

• Jul 12, 2012 · 7:00 PM

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 T.

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. :)

July 13, 2012

• ##### Benjamin

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

July 13, 2012

• ##### Vikas T.

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.blogspot.com/2012/06/boyer-moore-algorithm.html

July 13, 2012

• ##### A former member

Thanks Andy, Complex Algo made simple

July 13, 2012

• ##### Zach J.

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

July 13, 2012

• ##### max g.

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?

July 12, 2012

• ##### Benjamin

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

July 12, 2012

• ##### Jesse C.

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

July 12, 2012

• ##### Darren K.

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

July 12, 2012

• ##### Benjamin

Nope, you can come next time :)

July 12, 2012

• ##### Sidney San M.

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

July 12, 2012

• ##### 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 ;)

July 12, 2012

• ##### Vikas T.

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

July 11, 2012

• ##### Tom

no spots left?

July 11, 2012

• ##### 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 :)

July 11, 2012

• ##### Vikas T.

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

July 11, 2012

### 50 went

• ##### Kuldeep
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member
• A former member

### New York, NY

Founded Jan 31, 2010

#### Organizers:

Contact

Pivotal Labs

• ##### Vendavo

Vendavo is the leader in front-line profit optimization

• ##### Wolfram Research

Mathematica is the world's ultimate application for computations.

#### People in this Meetup are also in:

• ##### The New York Python Meetup Group

7,741 Python Programmers and Users

• ##### New York Open Statistical Programming Meetup

5,964 Data hackers

• ##### Data Visualization New York

3,570 Members

• ##### NYLUG - New York Linux Users Group

4,507 Members