Course: Data Structure and Algorithm $2.($a$)$ What is a rolling hash and how does it help in efficiently updating the hash value in the context of the Rabin$-$Karp algorithm?

$($b$)$ Why is it necessary to use the modulo operation in the hash function of the Rabin$-$Karp algorithm?

$($c$)$ You are given a DNA sequence and a pattern. The DNA sequence is represented by a series of nucleotides $($A$,$ C$,$ G$,$ and T$)$ which means the sequence contains only the letters A$,$ C$,$ G$,$ and T$.$ You need to figure out the number of occurrences of the given pattern in the DNA sequence using Rabin$-$Karp algorithm. You must show the Hash values and calculations for all the substrings.

The numeric values of each nucleotide are: $\backslash (\backslash$mathrm$\{$A$\}=1,\backslash$mathrm$\{$C$\}=2,\backslash$mathrm$\{$G$\}=3\backslash ),$ and $\backslash (\backslash$mathrm$\{$T$\}=4\backslash ).$

$```$

Sequence $=$ AGCTAGCGAGCTAG

Pattern $=$ AGCTAG

The hash function is as follows:

hash$($s$)=[\{$s$[0]*4^($n$-1)\}\backslash$operatorname$\{$mod$\}7+\{$s$[1]**\backslash$mp@subsup$\{4\}\{\}\{\backslash$wedge$\}($n$-2)\}\backslash$operatorname$\{$mod$\}7+\backslash$ldots$\backslash$ldots$..+\{$s$[$n$-1]**4^($n$-$n$)\}$

mod $7]\}\backslash$operatorname$\{$mod$\}$

where,

hash$($s$)=$ hash value of string s

n$\}=\backslash$mathrm$\{$ length of the string s

$```$