Suppose we are using the Rabin

$-$

Karp algorithm to search for a

$6$

$-$

character pattern

in the following string.

c g t c a a c c a t g t t c

If the alphabet for this string is

$\{$

a

$,$

$$c

$,$

$$g

$,$

$$t

$\}$

$,$

$$calculate the first hash value t

$0$

$$using Horner

$$

s

rule and a modulus of

$1$

$0$

$1$

$9$

$$and the remaining ti

$$

s using the O

$($

$1$

$)$

$$update rule. Show your

work.