Problem 93

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# String matching example

Due: April 29
Points: 4

Use the substring search algorithm we went over in class to search for the first occurrence of the substring 100101 in the following text:

$T = \mathtt{111001001100101010010011001001000110010}$

Use $$p=11$$ for your prime in the hash function $$h(x) = x \bmod p$$.

You should show how the rolling hash function is computed at each step. You can stop the search when it finds the first match.