liveBook · Manning

Rightmost occurrence

As explained in Algorithms Every Programmer Should Know

A rightmost occurrence is the latest-position occurrence of a character within a pattern or sequence.

When a pattern repeats a character, keep the shift for its rightmost occurrence before the final character. Earlier occurrences are overwritten so the shift does not skip a possible match. section 6.2

Repeated letters in “abcdabcy”

The letter “a” appears at indices 0 and 4. Their shifts are 7 and 3, so the rightmost occurrence sets the table value to 3. section 6.2

Table 6.3 Step-by-step bad character table construction for ‘abcdabcy’
Index (i)
character (pattern[i])
Shift = Length - 1 - index
Action taken
Current table state
initial
-
-
Default shift
[Default: 8]
0
a
8-1-0=7
Add new character
[a: 7]
1
b
8-1-1=6
Add new character
[a: 7, b: 6]
2
c
8-1-2=5
Add new character
[a: 7, b: 6, c: 5]
3
d
8-1-3=4
Add new character
[a: 7, b: 6, c: 5, d: 4]
4
a
8-1-4=3
Overwrite previous ‘a’
[a: 3, b: 6, c: 5, d: 4]
5
b
8-1-5=2
Overwrite previous ‘b’
[a: 3, b: 2, c: 5, d: 4]
6
c
8-1-6=1
Overwrite previous ‘c’
[a: 3, b: 2, c: 1, d: 4]
7
y
-
Ignore final character
[a: 3, b: 2, c: 1, d: 4]

See each repeated character overwrite its earlier shift as the table is built. section 6.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through shift calculations and overwriting repeated entries, while skipping the pattern’s final character.
Examples
Uses the pattern “abcdabcy” to show repeated a, b, and c entries being overwritten.
What you can do after
Build a bad-character shift table by keeping each repeated character’s rightmost eligible occurrence.
How it connects
Connects rightmost occurrences to Horspool’s algorithm and the bad-character shift table.

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.