liveBook · Manning

Bad character shift table

As explained in Algorithms Every Programmer Should Know

A lookup table that maps characters to safe distances for shifting a pattern after a mismatch in string searching.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through the construction formula, defaults, repeated characters, and exclusion of the final position, then demonstrates a lookup during search.
Examples
Constructs tables for “aabadc” and “abcdabcy” and traces a mismatch that produces a four-position shift.
What it assumes
Assumes familiarity with characters, indices, and patterns while teaching shift-table construction from its default value onward.
What you can do after
Build it from scratch for a pattern and use its entries to choose shifts during a Horspool search.
How it connects
Connects to Boyer–Moore–Horspool string matching, right-to-left scanning, and comparison with Knuth–Morris–Pratt and Rabin–Karp.

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.