CS 6301.502. Implementation of advanced data structures and algorithms
Fall 2017
Short Project 10: String algorithms
Fri, Nov 17, 2017

Version 1.0: Initial description (Fri, Nov 17).

Due: 11:59 PM, Sun, Dec 3.

Solve as many problems as you wish.  Maximum score: 50.

1. [50 points]
   Implement Tries.  Starter code is provided.

2. [50 points]
   Implement KMP algorithm.  Use it to solve the following problem:
   Given a string s, find the shortest string x such that x + s is a palindrome.

3. [50 points]
   Implement Boyer-Moore algorithm.

4. [50 points]
   Implement automata matcher.

5. [50 points]
   Implement Rabin-Karp algorithm for string matching.