In Horspool’s algorithm, a bad character is the text character at a mismatch during right-to-left comparison. Its shift-table value determines how far the pattern can move without risking a missed match; a character absent from the table gets the full pattern-length shift. section 6.1 section 6.2
Build the shift table before searching:
- For each pattern character except the last, use pattern length − 1 − index; repeated characters overwrite earlier values, preserving the rightmost occurrence. Characters absent from the table use the pattern length. section 6.1 section 6.2
A mismatch shifts the pattern
For “abcdabcy,” a mismatch on text character “d” uses shift 4, skipping four comparisons before the next alignment. 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]
|
The construction table shows how repeated characters overwrite earlier shift values. section 6.2
