One last algorithm we will be discussing for string search is the Boyer-Moore algorithm. The idea behind this approach is that it iterates through the bigger string from right to left. Consider the following example:
Find “ababac” in “abbdbeababacad”. We firstly align the strings as follows:
We compare ‘c’ with ‘e’. Since ‘e’ does not appear in the string we are searching for, so we know the match cannot occur for any of the positions 0, …, 5. Therefore we can move the smaller string 6 positions to the right, as follows:
Again, we compare ‘c’ with ‘c’, ‘a’ with ‘a’, and so on, until we notice that a matching has occurred. Next, we move one position to the right.
We compare ‘c’ with ‘a’ and, since a match does not occur, this means in theory we could move 5 positions to the right again. The algorithm stops here because this means we would exceed the capacity of the bigger string.