Will there be any advantage in comparing patterns and text characters from right to left rather than left to right?

Question

This is an exercise in Introduction to Designing and Analyzing Algorithms. This is a string matching problem. Say I have an ABCD string and have an XY pattern. And want to see if the string contains a pattern.

We just intend to use brute force here, so a comparison from left to right compares A with X, then compares B with X, etc. While a right-to-left comparison compares B with Y, next compares C to B. A hint says that a right-to-left comparison has an advantage, but I don't understand why.

Any hint is appreciated!

Answer 1

Yes.

see also

• Boyer-Moore String Search Algorithm

---

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

The earliest possible match, of course, begins at the beginning of the text. We are trying to match the pattern back, so we see if we can match D with the 4th character of the text.

  ? 12345678 ABCD 

This is not a coincidence, so we don’t know what not to try to match ABC with the first three characters. We also know (after linear preprocessing) that the character that we find, 4 , does not appear in the template at all, so the earliest possible match that we can find should start from the next position, that is, from the 5th character.

Again we try to match back, so we see if we can match D with the eighth character.

  ? 12345678 ABCD 

Find 8 ; this is not a coincidence. Therefore, the template is not displayed in the text. We needed to see only 2 characters from the text.

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

Answer 2

When you find that Y does not match B, what are the next two characters that you would compare? If you repeated these steps, how many comparisons would you make before covering the entire line? How many comparisons would you make using the brute force approach?