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:
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:
Source String | Operation | Result String |
---|---|---|
this | insert X | tXhis |
this | delete | tis |
this | replace X | tXis |
this | keep | this |
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:
Operation | Cost |
---|---|
insert | 1 |
delete | 1 |
replace | 1 |
keep | 0 |
Since the keep operation does not change anything, it has no associated cost.
In this assignment you have two options:
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 ^.
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:
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 additonional code needed for Program #2.
All the code for the program you submit should appear in a single C++ source file. Name Program #1 editdistance1.cpp. If you choose to do Program #2, name the file editdistance2.cpp.
Important: If you can get Program #1 to work but cannot get Program #2 to work correctly, please submit only Program #1.
A correct Program #1 is worth 8/10 points, and a correct Program #2 is worth 10/10 points.
Please submit either editdistance1.cpp or editdistance2.cpp (but not both) to eclass.e.southern.edu. Be sure to include the appropriate comments.