Summer 2003: Algorithm Library Design --
Projects
Project: Exact String Matching
The exact string matching problem is to find a short string such as a word
in a long string such as a file. An introduction to
exact string matching can be found in the
lecture
notes of the course Data
Structures and Algorithms (Winter 01/02). More information
including over 30 algorithms with implementations in C can be found
here.
STL has an exact string matching algorithm under the name
search.
The implementation of search uses an algorithm known as
the brute force or naive algorithm. There are more efficient
algorithms (both in theory and in practice)
but they are less generic, which means they
place more restrictions on one or more of the following:
- iterator category
- properties of characters
- properties of the comparison operator
The goal of the project is to design and implement a version of
search that uses more efficient algorithms
when possible. The tasks include:
- Choose a set of algorithms offering different tradeoffs between
genericity and speed, and implement a generic version of them in C++.
- Design and implement a common user interface that automatically
selects the algorithm using, for example, traits techniques.
- Document the design, for example, in the style of
STL documentation at SGI.