This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 99

String matching example

Due: May 3
Points: 3

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.