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
