liveBook · Manning

Shift value

As explained in Algorithms Every Programmer Should Know

A shift value is an integer distance specifying how far a search pattern may move after a character mismatch.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Derives table entries from a formula and explains defaults, repeated characters, and omission of the final pattern character.
Examples
Works through shift tables for “aabadc” and “abcdabcy,” including repeated-character overwrites.
What it assumes
Assumes familiarity with pattern positions and mismatches, then derives table values through worked examples.
What you can do after
Build a bad-character shift table using pattern positions, rightmost occurrences, and a default distance.
How it connects
Connects shift values to Horspool’s algorithm and the bad-character shift table.

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.