Would there be any advantage in comparing pattern and text characters right-to-left instead of left-to-right?

Question

This is the exercise in "Introduction to The Design and Analysis of Algorithms". It's a string matching issue. Say I have string ABCD, and have a pattern XY. And want to see if the string contains the pattern.

We just assume to use brute-force here, so the left-to-right comparison is comparing A with X, next is comparing B with X, etc. While right-to-left comparison is comparing B with Y, next is comparing C with B. The hint says right-to-left comparison does have the advantage, but I don't see why.

Any hint is appreciate!

Answer 1

Yes.

See also

• Boyer–Moore string search algorithm

---

As an extreme example, consider if we need to find the pattern ABCD in the text 12345678.

The earliest possible match of course starts at the beginning of the text. We try to match the pattern backward, so we see if we can match D with the 4th character of the text.

   ?    
12345678
ABCD

This is not a match, so we know there's no point in trying to match ABC with the first 3 characters. We also know (after linear time pre-processing) that the character we find, 4, doesn't appear in the pattern at all, so the earliest possible match we can find must start at the next position, i.e. 5th character.

Again we try to match backward, so we see if we can match D with the 8th character.

       ? 
12345678
    ABCD

We find 8; this is not a match. Therefore the pattern doesn't appear in the text. We only needed to see 2 characters from the text.

This is one important characteristics of the Boyer-Moore algorithm: for a text of length N and a fixed pattern of length M, the average-case performance is N/M comparison. That is, perhaps somewhat counterintuitively at first, the longer the pattern we are looking for, the faster we can usually find it.