Edit Distance

Given two text strings A and B, the problem is to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B. In this problem, you will write a program to compute the edit distance between different pairs of strings

Input: edit.in

The input file (edit.in) will contain an unknown number of pairs of strings. Each string will appear on a separate line in the input file.

Sample Input File

kitten
sitting
bozeman
leipzig

Output: edit.out

For each pair of strings, the edit distance between the two strings should be printed in a file named edit.out. Match the output format below exactly.

Sample Output File

The edit distance between kitten and sitting is 3
The edit distance between bozeman and leipzig is 7