This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
In class, we looked at the substring search problem: Given a text file with \(n\) characters, and a string \(s\) of length \(m\) (obviously \(m\le n\)), we want to find the first occurrence of \(s\) within the file.
(This is also sometimes called "string matching".)
The Boyer-Moore algorithm and Knuth-Morris-Pratt (KMP) algorithm are the two most famous deterministic algorithms for this problem. In class, we also looked at the Karp-Rabin randomized algorithm for this problem.
Do a little research and discover the running times of these three algorithms. Report the worst-case running time of BM and KMP, and the expected running time of KR. When do you think one would be more useful than the others?