Assignment 1, due Wednesday, 21 September

Implement the Z algorithm as given on page 9 of the text (and here) in C, C++, Java, or Perl. (If you wish to use a different language, please check with me in advance.) When called with no arguments your program should read from standard input and output some statistics to standard output. These statistics should include the number of times cases I, IIa, and IIb are executed and some others that you find interesting. Possibilities include:

For debugging purposes, you may want to give your program a command-line or compile-time flag that causes it to output the values of Z, l, r and the case number for each input letter. When you're convinced you've implemented the algorithm correctly, test it on a variety of input files and see how the statistics change according to type of file. Possible input files include:

To hand in: