Boyer-Moore Algorithm

Alagesan Palani

Unlike Knuth-Moriss-Pratt linear time algorithm, Boyer-moore algorithm can search for a pattern in a sublinear time. Till KMP time, people worked hard to come up with an algorithm to search for a pattern in linear time, i.e., O(M+N) time where M is the total length of the pattern to search and N is the total length of the String searched from.

Boyer and Moore were curious to nail down an algorithm which can work more efficiently than KMP in sublinear time. By “Sublinear” Boyer-moore means, this can search a pattern from the string by inspecting minimum number of characters rather than inspecting every character in the string. They deviced an intellectual logic to skip inspecting some characters and still reached a successful search match when the pattern existed in the string.

Though Boyer-moore algorithm works efficiently in sublinear time, this has few limitations in which case it will end up…

View original post 920 more words

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on June 3, 2013, in Programming. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: