Analysis of Algorithms : An Active Learning Approach

5.3 PROGRAMMING EXERCISES 139

5.2.2

1. Construct the approximate matches matrix for substring “their” and text
   “hello there friends.”


2. Construct the approximate matches matrix for substring “where” and text
   “were they here.”


3. When we looked for an exact match, we could determine the starting point
   easily, because we knew the start had to be S characters from the end. With
   approximate matching, finding the start of the match is not so easy because
   of the possibility of characters missing from the substring, the text, or both.
   Give a detailed description of what data structure and process you would
   add to the algorithm described in this lesson to have that information avail-
   able when a k-approximate match is found. (Hint: One way to see if the
   parenthesis in an expression match is to keep a counter as you scan the
   expression, adding 1 to it on every open parenthesis, subtracting 1 from it
   on every close parenthesis, and not changing it for other characters. Can
   you do something similar to keep track of missing characters?)

5.3 Programming Exercises

You can get a large block of text to use for these programming problems by

saving a term paper you wrote using a word processor in text-only format. To

be able to test special cases, put in a word that is not already there. Options for

this word might be a plant or flower, the name of a place, or a color name. Be

careful in your choice of words, because a short word may appear as part of

other words. For example, red is part of bothered. Using this technique, you

could put the word “banyan” someplace in the middle of the text and the word

“potato” at the end, and then search for those words.

1. Program up the Knuth-Morris-Pratt algorithm and count the number of
   character comparisons done for a few different cases. Don’t forget to count
   the comparisons done in the calculation of the failure links. Be sure to test
   both long and short patterns. Your program should output the location in
   the text (distance from the start) where the pattern was found and how
   many comparisons were done. How do your results compare to the analysis
   done in the text?

■5.2.2 EXERCISES