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