The edit distance between two words is the fewest single-character insertions, deletions and substitutions that turn one into the other — the measure behind "did you mean…?".
Write EditDistance. For each pair of words, fill the table d[i][j] (distance between the first i letters of a and the first j letters of b), print the distance, then trace back one optimal list of operations, and — when both words have at most 8 letters — the last row of the table.
For the input
kitten sitting
the program prints
kitten -> sitting: 3 edit(s)
operations: replace k>s; replace e>i; insert g;
last row: 6 6 5 4 3 3 2 3
Several optimal operation lists can exist, so the operations: line is not checked by the tests (the distance and the last row are).