Problem $2.(40$ points$)$

Consider the problem of searching for genes in DNA sequences using Horspool's algorithm. A

DNA sequence consists of a text on the alphabet $\{$A$,$C$,$G$,$T$\}$ and the gene or gene segment is

the pattern.

a$.$ Construct the shift table for the following gene segment of your chromosome $10$:$(20$ p$.)$

TCCTATTCTTT

b$.$ Apply Horspool's algorithm to locate the above pattern in the following DNA sequence: $(20$

p$.)$

TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTTT

Kindly write the solution on a paper and match character to character in the string matching. Also Explain in easy steps how the horspool's algorithm actually works. The problem I am having is with the A value in shift table I have $6$ as a value and I get over a T for the starting pattern in the string, hence stuck.