Edit Distance
Problem Description
Given a string, an edit script is a set of instructions to turn itinto another string. There are
three kinds of operations in an edit script:
Add: Output one character. This instruction does not consume any characters
from the source string.
Delete: Delete one character. That is, consume one character from the source string and output nothing.
Modify: Modify one character. That is, consume one character from the source string and output a character.
Now, We define that the edit distance is the minimal number of operations to change string A into string B.
Given two strings, find the edit distance from string A to string B.
Input
There are several test cases in the input.
The first line of each test case is two integers n and m (1 <= n,m <= 1000), indicate the length of the two strings. Then two lines are string A and string B.
The input is ended by EOF.
Output
For each test cases, please output the edit distance from string A to string B.
Sample Input
1 2
a
aa
2 2
aa
ab
Sample Output
1
1
原来以为是求最长子序列一下wa了，后来发现不是，状态转移方程是：
当a[i-1]等于b[j-1]时，状态转移为res[i][j]=res[i-1][j-1]否则,res[i][j]=MIN(res[i-1][j-1]+1,res[i][j-1]+1,res[i-1][j]+1)。
#include <stdio.h>
#include<string.h>
#define min_l(a,b,c) a<b?(a<c?a:c):(b<c?b:c)
int a_len,b_len;
int dis[1010][1010];
void max_dis(char *a,char *b){
//memset(dis,0,sizeof(int)*1010*1010);
for(int i = 1; i <=a_len; ++i){
for(int j = 1;j <=b_len;++j){
if(!(a[i - 1] - b[j - 1])){
dis[i][j] = dis[i-1][j-1];
}else{
dis[i][j] = min_l(dis[i - 1][j] + 1,dis[i][j-1] + 1,dis[i-1][j-1] + 1);
}
}
}
return ;
}
int main(int argc, char *argv[])
{
char a[1100],b[1100];
for(int i = 0; i < 1010;++i){
dis[0][i] = i; //a 的长度为0 b的长度为i时的最大编辑距离
dis[i][0] = i; //b 的长度为0 a的长度为i时的最大编辑距离
}
while(~scanf("%d%d",&a_len,&b_len)){
scanf("%s%s",a,b);
max_dis(a,b);
printf("%d\n",dis[a_len][b_len]);
}
return 0;
}