In Horspool’s algorithm, a shift value tells how many positions to move the pattern after a mismatch. The value comes from the mismatching text character: use its table entry, or the pattern length if it has no entry. section 6.1
Build the bad-character shift table before searching:
- For each pattern character except the last, calculate pattern length − 1 − its index. section 6.1
- If a character occurs more than once, keep the value from its rightmost occurrence; set the default for absent characters to the pattern length. section 6.1
Pattern “abcdabcy”
The pattern has length 8. Its table assigns a shift of 3 to “a,” 2 to “b,” 1 to “c,” and 4 to “d”; the default is 8. The later occurrences overwrite earlier values, and the final “y” is omitted. section 6.2
Table 6.2 Final Bad Character Table for ‘aabadc’
|
Character
|
Value
|
|
d
|
1
|
|
a
|
2
|
|
b
|
3
|
|
default
|
6
|
See the completed shift table for “aabadc,” including its default value. section 6.1
