Problem 89

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

Substring search algorithms

Due: April 26
Points: 2

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?