Edit distance is to measure the difference between two strings. There are three types of edit operations that can be used to change a given string S:
(1) Substitution: replace a character of S by a different character. For example, “cut” can be changed to “cat” by replacing “u” with “a”.
(2) Insertion: insert a single character into S. For example, “cat” can be changed to “cats” by inserting “s” at the end of “cat”.
(3) Deletion: delete a single character from S. For example, “cats” can be changed to “cat” again by deleting “s” from “cats”.
Given two strings S1 and S2, the edit distance between S1 and S2 is defined as the minimum number of edit operations required to transform S1 to S2.
Each case consists of two lines. Each line contains a string of lowercase characters, with the first line representing S1 and the second representing S2. The length of each string is no more than 4000.
Print the edit distance between S1 and S2.
Suppose that S1 and S2 are strings with n and m characters, respectively. Let S1[1..n] and S2[1..m] denote these two strings. Now, we can define a function Dist(x, y) to give the edit distance between the strings S1[1..x] and S2[1..y]. It is easy to check that Dist(x, y) satisfies the following rules:
●Dist(x, 0) = x for all x = 0, 1, 2, …, n;
●Dist(0, y) = y for all y = 0, 1, 2, …, m;
●Dist(x, y) = min { Dist(x – 1, y)+1, Dist(x, y – 1)+1, Dist(x – 1, y – 1)+a } if x > 0 and y > 0, where a = 1 if S1[x] is not the same as S2[y]; otherwise, a = 0.
The required answer will be the value of Dist(n, m).
You should store the value of each entry Dist(i, j) or you may not pass all of the test case