Question

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

i) Pattern1:   AABCACCCA

ii) Pattern 2: CCCAAABBD

iii) Pattern3:  ABCABCBAD

iv) Pattern4:   BSDGSBAA

Answer 1

1. pattern 1 = AABCACCCA

index = 012345678

length = 9

Letter	A	B	C	*
value	1	6	1	9

calculating the value of each letter in the pattern:

value formula is given by: max(1,length-index-1)

values :

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

A= max(1,9-1-1)=7

B= max(1,9-2-1)=6// this value is updated in the table as it is the rightmost one

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

A= max(1,9-4-1)=4

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

C= max(1,9-6-1)=2

C= max(1,9-7-1)=1// this value is updated in the table as it is the rightmost one

A= max(1,9-8-1)=1 // this value is updated in the table as it is the rightmost one

2. pattern 1 = CCCAAABBD

index = 012345678

length = 9

Letter	A	B	C	D	*
value	3	1	6	1	9

calculating the value of each letter in the pattern:

value formula is given by: max(1,length-index-1)

values :

C= max(1,9-0-1)=8

C= max(1,9-1-1)=7

C= max(1,9-2-1)=6// this value is updated in the table as it is the rightmost one

A= max(1,9-3-1)=5

A= max(1,9-4-1)=4

A= max(1,9-5-1)=3// this value is updated in the table as it is the rightmost one

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

B= max(1,9-7-1)=1// this value is updated in the table as it is the rightmost one

D= max(1,9-8-1)=1 // this value is updated in the table as it is the rightmost one

3.pattern 1 = ABCABCBAD

index = 012345678

length = 9

Letter	A	B	C	D	*
value	1	2	3	1	9

calculating the value of each letter in the pattern:

value formula is given by: max(1,length-index-1)

values :

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

B= max(1,9-1-1)=7

C= max(1,9-2-1)=6

A= max(1,9-3-1)=5

B= max(1,9-4-1)=4

C= max(1,9-5-1)=3// this value is updated in the table as it is the rightmost one

B= max(1,9-6-1)=2// this value is updated in the table as it is the rightmost one

A= max(1,9-7-1)=1// this value is updated in the table as it is the rightmost one

D= max(1,9-8-1)=1 // this value is updated in the table as it is the rightmost one

4.pattern 1 = BSDGSBAA

index = 01234567

length = 8

Letter	A	B	D	G	S	*
value	1	2	5	4	3	8

calculating the value of each letter in the pattern:

value formula is given by: max(1,length-index-1)

values :

B= max(1,8-0-1)=7

S= max(1,8-1-1)=6

D= max(1,8-2-1)=5// this value is updated in the table as it is the rightmost one

G= max(1,8-3-1)=4// this value is updated in the table as it is the rightmost one

S= max(1,8-4-1)=3// this value is updated in the table as it is the rightmost one

B= max(1,8-5-1)=2// this value is updated in the table as it is the rightmost one

A= max(1,8-6-1)=1

A= max(1,8-7-1)=1// this value is updated in the table as it is the rightmost one

Only the right most values are to be filled into the table as per the algorithm