Question

Using the Boyer-Moore algorithm, find the Bad Match table for the below patterns.

Pattern1: AABCACCCA

Pattern 2: CCCAAABBD

Pattern3: ABCABCBAD

Pattern4: BSDGSBAA

Answer 1

Boyer-Moore algorithm to identify the Bad Match table

Step 1: First, take the string pattern and then index each character of the string beginning from the 0 (ignore the last character).  

Step 2: Calculate the length of the string pattern.

Step 3: Draw a skeleton of the bad match table that involves only the unique character and a special symbol at the end of the table.  

Step 4: Now, to fill the values of characters in the table, traverse the pattern from start to second last.  

Step 5: For each character of the pattern, calculate the value max(1, length-index-1).

Step 6: If the same character repeats then update the character value as per the new index.  

Note-

1) If the last character of the pattern does not occur before, the value of the character will be the same as the length of the pattern.

2) The value of the special symbol will be the length of the pattern.

Example 1:

Pattern	A	A	B	C	A	C	C	C	A
Index	0	1	2	3	4	5	6	7	8

Length = 9

Skeleton of bad match table

Characters	A	B	C	*
Values

Calculate the value of each character in the pattern(formula = max(1, length-index-1))

Value(A) = max(1, 9-0-1) = max(1, 8) = 8

Value(A) = max(1, 9-1-1) = max(1, 7) = 7 = new value(A)

Value(B) = max(1, 9-2-1) = max(1, 6) = 6

Value(C) = max(1, 9-3-1) = max(1, 5) = 5

Value(A) = max(1, 9-4-1) = max(1, 4) = 4 = new value(A)

Value(C) = max(1, 9-5-1) = max(1, 3) = 3 = new value(C)

Value(C) = max(1, 9-6-1) = max(1, 2) = 2 = new value(C)

Value(C) = max(1, 9-7-1) = max(1, 1) = 1 = new value(C)

Value(A) = max(1, 9-8-1) = max(1, 0) = 1 = new value(A)

Value(*) = length of the pattern = 9

The final bad match table of the AABCACCCA

Characters	A	B	C	*
Values	1	6	1	9

Hence, follow the same procedure for the remaining patterns.

Example 2:

Pattern = CCCAAABBD

Length = 9

Bad match table

Characters	C	A	B	D	*
Values	6	3	1	9	9

Note - D is the last character of the pattern and it does not occur before. Therefore, the value of D will be equal to the length of the pattern.

Example 3:

Pattern = ABCABCBAD

Length = 9

Bad match table

Characters	A	B	C	D	*
Values	1	2	3	9	9

Example 4:

Pattern = BSDGSBAA

Length = 8

Bad match table

Characters	B	S	D	G	A	*
Values	2	3	5	4	1	8