liveBook · Manning

Preprocessing

As explained in Algorithms Every Programmer Should Know

Preprocessing is preparatory computation performed on input data before the main algorithmic operation begins.

Preprocessing prepares data before a search begins. In string matching, it can build a table that helps the search skip ahead, trading setup time and memory for faster searching. section 5.3.1 section 6.1

The costs depend on the algorithm: KMP spends O(m) time and auxiliary space constructing its LPS array. Horspool builds a bad-character table by scanning the pattern, adding characters and overwriting earlier entries so each keeps the rightmost occurrence’s shift. section 5.3.1 section 6.1

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 construction of a bad-character table for the pattern “aabadc,” including how repeated characters update their shifts. section 6.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through bad-character-table construction, while quantifying LPS-array costs without detailing its construction.
Examples
Contrasts LPS-array construction with a stepwise bad-character table for the pattern “aabadc.”
What you can do after
Build it from scratch by calculating and overwriting Horspool bad-character shifts for a pattern.
How it connects
Connects preprocessing to Knuth–Morris–Pratt and Horspool string-search algorithms.

Also explained in

Compare how 25 books explain preprocessing →

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.