liveBook · Manning

Bad character

As explained in Algorithms Every Programmer Should Know

A bad character is a text character that causes a right-to-left pattern comparison to mismatch and determines a pattern shift in Horspool's algorithm.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Constructs the shift table using a formula, rightmost-occurrence overwrites, and a default shift for absent characters.
Examples
Works through shift tables for “aabadc” and “abcdabcy,” including a mismatch on “d” that shifts four positions.
What you can do after
Apply it via Horspool’s algorithm to select shifts after mismatches without skipping valid matches.
How it connects
Connects bad-character shifts to Horspool’s algorithm and Boyer-Moore-Horspool pattern searching.

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.