Implement the Rabin$-$Karp search algorithm as presented in the exercise. A hash value is calculated for the pattern $($of length

m$),$ and for a partial sequence from the text $($with the same length m$).$ If the two hash values are equal, the brute$-$force method

is used to verify character by character if the pattern and the sequence are identical. Implement the rolling$-$hash function for

computing the hash values for base b$=29,$ using the following skeleton: class RabinKarp:

# param pattern $-$ The string pattern that is searched in the text.

# param text $-$ The text string in which the pattern is searched.

# return a list with the starting indices of pattern occurrences in the text, or None if not found.

# raises ValueError if pattern or text is None or empty.

def search$($self$,$ pattern, text$)$:

# param sequence $-$ The char sequence for which the $($rolling$)$ hash shall be computed.

# param last$\_$character $-$ The character to be removed from the hash when a new character is added.

# param previous$\_$hash $-$ The most recent hash value to be reused in the new hash value.

# return hash value for the given character sequence using base $29.$

def get$\_$rolling$\_$hash$\_$value$($self$,$ sequence, last$\_$character, previous$\_$hash$)$: The search method should return a list with the starting indices of the positions where the pattern was found in the input text,

or None if not found.

The alphabet of the input text and pattern is letters $($upper$-$ and lower case$),$ spaces $(),$ periods $(.)$ and commas $(,),$ and

the match must be case sensitive$.$ None or empty strings in the pattern or text should trigger a ValueError exception. In case

of partially overlapping matches, as in the example below $($see index $11$ and $12),$ all of them should be counted.

Example: For sequence $$AbCdExxx$,$ Xxxxxke$$ and pattern $$xxx$$ the search should return $[5,11,12].$ and here is the provided code: class RabinKarp:

def $\_\_$init$\_\_($self$)$:

pass

$"""$

This method uses the RabinKarp algorithm to search a given pattern in a given input text.

@ param pattern $-$ The string pattern that is searched in the text.

@ param text $-$ The text string in which the pattern is searched.

@ return a list with the starting indices of pattern occurrences in the text, or None if not found.

@ raises ValueError if pattern or text is None or empty.

$"""$

def search$($self$,$ pattern, text$)$:

# TODO

pass

$"""$

This method calculates the $($rolling$)$ hash code for a given character sequence. For the calculation use the

base b$=29.$

@ param sequence $-$ The char sequence for which the $($rolling$)$ hash shall be computed.

@ param last$\_$character $-$ The character to be removed from the hash when a new character is added.

@ param previous$\_$hash $-$ The most recent hash value to be reused in the new hash value.

@ return hash value for the given character sequence using base $29.$

$"""$

@staticmethod

def get$\_$rolling$\_$hash$\_$value$($sequence$,$ last$\_$character, previous$\_$hash$)$:

# TODO

pass