Beginning Java Data Structures and Algorithms

The Bad Character Rule

The idea of the bad character rule is to identify mismatches between a character in the pattern and a character in the text so that we can safely skip certain shifts. To identify the occurrence of a bad character, let's look at the example in the following table:

i

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

T

H

C

B

B

A

H

C

C

A

B

A

H

A

H

B

C

C

P

A

B

A

H

A

H

Table 5.1: Identifying bad characters

In the example provided in Table 5.1, we successfully matched the suffix AH, but then arrived at a bad character, since B != H. Whenever this happens, we're sure that it will only be possible to find a valid shift starting from the next shift that solves this mismatch. This means that we can shift P until either ...