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.