Imagine searching a long document for a short word. When a character in the text cannot help complete the match, moving the pattern just one place wastes work. A bad character shift table lets Horspool’s string-search algorithm look up how far to move the pattern instead. section 6.0
Build the table once for the pattern, before searching:
- Use the pattern’s length as the default shift for characters with no table entry. section 6.1
- Visit each pattern position except the last. For a character at index i, store length − 1 − i. section 6.1
- Let later occurrences overwrite earlier ones. This keeps the rightmost eligible occurrence and avoids an overly large shift. Excluding the final position also prevents a zero shift. section 6.2 section 6.5
A six-character pattern
For “aabadc”, the entries are a → 2, b → 3, and d → 1; every character without an entry gets the default shift 6. The three appearances of “a” produce successive values 5, 4, and 2, so only 2 remains. The final “c” is not entered. section 6.1
During a search, Horspool compares each aligned window from right to left and uses the table to skip ahead after a mismatch. For “abcdabcy”, a window ending in text character “d” mismatches the pattern’s “y”; looking up “d” gives a shift of 4. The tradeoff is preprocessing and memory: for very short patterns, building a table may cost more than the skipped comparisons save. section 6.2 section 6.3
Table 6.1 Step-by-step bad character table construction for ‘aabadc’
|
Index (i)
|
character (pattern[i])
|
Shift = Length - 1 - index
|
Action taken
|
Current table state
|
|
initial
|
-
|
-
|
Default shift
|
[Default: 6]
|
|
0
|
a
|
6-1-0=5
|
Add new character
|
[a: 5]
|
|
1
|
a
|
6-1-1=4
|
Overwrite previous ‘a’
|
[a: 4]
|
|
2
|
b
|
6-1-2=3
|
Add new character
|
[a: 4, b: 3]
|
|
3
|
a
|
6-1-3=2
|
Overwrite previous ‘a’
|
[a: 2, b: 3]
|
|
4
|
d
|
6-1-4=1
|
Add new character
|
[a: 2, b: 3, d: 1]
|
|
5
|
c
|
-
|
Ignore final character
|
[a: 2, b: 3, d: 1]
|
Follow the row-by-row construction for “aabadc” to see repeated entries overwritten and the last character skipped. section 6.1
