Please read the remarks about programming problems for this course.

You will use dynamic programming techniques to implement a solution to the edit distance problem.

The edit distance problem is this: Given two strings, s and t, what is the minimal number of edit operations required to convert s into t? The edit distance problem has several practical applications:

• In order for a word processor to autocorrect a misspelled word it must compute the closest word (or several close words) in its dictionary that matches the user's supplied word. The difference between the user supplied misspelled word and a good candidate word is the edit distance.

• In genone research the edit distance can be used to align and test the similarities between two DNA sequences. In DNA, the "characters" are the A (adenine), T (thymine), G (guanine), and C (cytosine) nucleotide bases, and the "string" is the sequence of these bases. Here computational biologists can use the edit distance to detect genes that have similar functions.

• Other applications include plagarism detection, version control systems, and speech recognition.

Edit operations consist of inserting a character (insert), deleting a character (delete), substituing one character for another (replace), and leaving a character unchanged (keep). Suppose you have the string this, where the underline represents the current position within the string. The following table shows the results of the various edit operations:

Note that the keep operation simply leaves the current character as is and moves the current position to the next character. Each one of these operations has an associated cost. The following table lists the costs for each operation for the purposes of this assignment:

Since the keep operation does not change anything, it has no associated cost.

In this assignment you have two options:

1. Compute the minimal number of editing operations required to transform from one string into another string. This is a single non-negative integer value.

   The program should accept two strings from the standard input stream, each on its own line (use getline), and print the number that represents the minimal edit distance between the two strings. The program should loop, continuously requesting strings and printing the edit distance between the strings until the user enters a blank line.

   The following shows a sample run of program #1:

            computer 
            commuter
            1
            this 
            those
            2
            approximate string matching 
            appropriate student mixing
            11
            

   For reasons noted below, your strings may not contain any of the characters +, -, /, or ^.

2. Compute the minimal number of editing operations required to transform one string into another string. Then provide the sequence of editing operations required to perform the transformation. This sequence of operations is to be encoded in an editing string described below.

   Edit String Symbol	Meaning
   +c	Insert character c
   -	Delete current character
   /c	Replace current character with c
   ^	Keep current character

   The program should accept two strings from the standard input stream, each on its own line (use getline). In response to the two input strings the program should print the minimal edit distance between the two strings, then print a colon (:), and finally print a minimal edit string that can be used to transform the first string into the second string. The program should loop, continuously requesting strings and printing the edit distance between the strings and edit strings until the user enters a blank line.

   The following shows a sample run of program #2:

            computer 
            commuter
            1:  ^^^/m^^^^
            this 
            those
            2:  ^^/o^+e
            approximate string matching 
            appropriate student mixing
            11:  ^^^^^/p/r/i^^^^^^+u/d/e^/t^^--/i/x^^^
            

   Your input strings may not contain any of the characters +, -, /, or ^, since these characters constitute special action symbols in the edit string.

   The understand the above output:

   • In the first case above, the first three characters are the same (^^^) the fourth character must changed from a p to an m (/m), and the remaining four characters are the same (^^^^).
   • In the second case above, the first two characters are the same (^^) the third character must changed from an i to an o (/o), the s needs no change (^), and finally an e must be added (+e).
   • The last case shows a number of changes, including two deletions (--).

Since the second program is just an extension of the first program, begin working on the first program. Once you are confident that the first program is working correctly, you may begin working on the additional code needed for Program #2.

All the code for the program you submit should appear in a single C++ source file. If you complete only Program #1, name your program yourlastname-1.cpp. If you choose to do Program #2, name the file yourlastname-2.cpp. For example, if I completed Program #2, I would submit halterman-2.cpp as my source file.

Important: If you can get Program #1 to work but cannot get Program #2 to work correctly, please submit only Program #1. A non-compiling, non-working, or crashing Program #2 will receive no more credit than a similarly behaving Program #1.

A correct Program #1 is worth 8/10 points, and a correct Program #2 is worth 10/10 points.

Please submit either Program #1 or Program #2 (but not both) to eclass.e.southern.edu. Be sure to include the appropriate comments.