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
























