liveBook · Manning

Right-to-left processing

As explained in Algorithms Every Programmer Should Know

Right-to-left pattern scanning compares a candidate pattern occurrence beginning with its rightmost character and proceeds toward its leftmost character.

Right-to-left processing compares a candidate pattern occurrence from its final character toward its first. In Horspool’s algorithm, a mismatch triggers a lookup of the mismatching text character in the bad character shift table, allowing the search window to advance instead of shifting blindly by one. section 6.0 section 6.1

Compare from the pattern’s end

For the pattern “abcdabcy,” the first comparison checks the text character “d” against the pattern’s final “y.” On a mismatch, the table assigns “d” a shift of four, so the search window advances four positions. section 6.2

Figure 6.2 The letter ‘d’ in the text is compared with ‘y’ in the pattern as scanning is done from right to left. It’s a mismatch. So, checking the bad character table for the letter ‘d’ from table 6.4, the corresponding shift value is 4. The pattern is shifted by 4, and successfully 4 character comparisons were skipped.

The figure traces the initial mismatch, the lookup for “d,” and the resulting four-position shift. section 6.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through comparisons and mismatch shifts, including a pattern walkthrough and shift-table construction.
Examples
Traces the pattern “abcdabcy” against text, including a mismatch on “d” and a four-position shift.
What you can do after
Build it from scratch by constructing a shift table and scanning text windows from right to left.
How it connects
Connects to string matching, the Boyer–Moore–Horspool algorithm, and bad character shift tables.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.