Assignment

Implement the Rabin-Karp algorithm. Write a Python function firstOccurrence that takes as parameters a text T and a pattern P (both consisting of 0’s and 1’s). The function returns the index of the first occurrence of the pattern P in the text T, -1 if P does not occur in T.

Implement a version of the Rabin-Karp algorithm that works for the DNA-alphabet of size 4 (characters A, T, C, G) as a Python function firstOccurrenceDNA, with parameters as before.

Examples

>>> firstOccurrence("0101010001", "000")
6
>>> firstOccurrence("0101010101000", "000")
10
>>> firstOccurrence("0100100100110", "000")
-1

>>> firstOccurrenceDNA("ATTATTAAA", "AAA")
6
>>> firstOccurrenceDNA("AATTATTATCGATTACGGA", "AAA")
-1