Question

SHOW WORK

. Using the Boyer-Moore algorithm, find the Bad Match table for the below patterns.                                                                                                   (8 points)

i) Pattern1:   AABCACCCA

ii) Pattern 2: CCCAAABBD

iii) Pattern3:  ABCABCBAD

iv) Pattern4:   BSDGSBAA

SHOW WORK

Answer 1

i) Pattern1:   AABCACCCA

Steps 1: Index each character in pattern starting from 0.

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

step 2:take length of the pattern, here that is 9.

step 3: calculate 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

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

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

value(A)=max(1,9-6-1)=max(1,2)=2

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

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

If the same characters repeats, update the table by the values from the new character

Pattern	A	B	C	*
Values	1	6	3	9

ii) Pattern 2: CCCAAABBD

Steps 1: Index each character in pattern starting from 0.

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

step 2:take length of the pattern, here that is 9.

step 3: calculate max(1,length-index-1)

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

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

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

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

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

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

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

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

value(D)=max(1,9-0-1)=max(1,0)=1

If the same characters repeats, update the table by the values from the new character

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

iii) Pattern3:  ABCABCBAD

Steps 1: Index each character in pattern starting from 0.

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

step 2:take length of the pattern, here that is 9.

step 3: calculate max(1,length-index-1)

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

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

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

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

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

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

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

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

value(D)=max(1,9-0-1)=max(1,0)=1

If the same characters repeats, update the table by the values from the new character

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

iv) Pattern4:   BSDGSBAA

Steps 1: Index each character in pattern starting from 0.

Pattern	B	S	D	G	S	B	A	A
Index	0	1	2	3	4	5	6	7

step 2:take length of the pattern, here that is 9.

step 3: calculate max(1,length-index-1)

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

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

value(D)=max(1,8-2-1)=max(1,6)=5

value(G)=max(1,8-3-1)=max(1,5)=4

value(S)=max(1,8-4-1)=max(1,4)=3

value(B)=max(1,8-5-1)=max(1,3)=2

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

value(A)=max(1,8-7-1)=max(1,0)=1

If the same characters repeats, update the table by the values from the new character

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