文档介绍：第四次课:动态规划
Content
Edit Distance
.:8080/JudgeOnline/showproblem?problem_id=1430
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。
Input
第一行是字符串A,文件的第二行是字符串B。
Output
输出距离d(A,B)
Sample Input
fxpimu xwr
Sample Output
5
But how can pute the edit distance? We can define a recursive algorithm using the observation that the last character in the string must either be matched, substituted, inserted, or deleted. Chopping off the characters involved in the last edit operation leaves a pair of smaller strings. Let i and j be the last character of the relevant prefix of s and t, respectively. There are three pairs of shorter strings after the last operation, corresponding to the strings after a match/substitution, insertion, or deletion. If we knew the cost of editing the three pairs of smaller strings, we could decide which option leads to the best solution and choose that option accordingly.
#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */
int pare(char *s, char *t, int i, int j)
{
int k; /* counter */
int opt[3]; /* cost of the three options */
int lowest_cost; /* lowest cost */
if (i == 0) return(j * indel(’’));
if (j == 0) return(i * indel(’’));
opt[MATCH] = pare(s,t,i-1,j-1) + match(s[i],t[j]);
opt[INSERT] = pare(s,t,i,j-1) + indel(t[j]);
opt[DELETE] = pare(s,t,i-1,j) + indel(s[i]);
lowest_cost = opt[MATCH];
for (k=INSERT; k<=DELETE; k++)
if (opt[k] < lowest_cost) lowest_cost = opt[k];
return( lowest_cost );
}
This program is absolutely correct – convince yourself. It is also impossibly slow. Running on puter, it takes several seconds pare two 11-character strings, and putation disappears into never-never land on anything longer.
Why is the algorithm so slow? It takes exponential time because it pu