编辑距离

题目描述
Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。
Ex：
字串串A:abcdefg
字符串B: abcdef
通过增加或是删掉字符”g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：
给定任意两个字符串，写出一个算法计算它们的编辑距离。
本题含有多组输入数据。

输入描述:
每组用例一共2行，为输入的两个字符串
输出描述:
每组用例输出一行，代表字符串的距离

示例1
输入
abcdefg
abcdef
abcde
abcdf
abcde
bcdef
输出
1
1
2

题目分析：

Levenshtein Distance距离，实现思路动态规划：
(1)初始化dis[0][0]~dis[0][m],m为字符串a的长度，初始化dis[0][0]~dis[n][0],n为字符串a的长度，其中dis[n+1][m+1]为编辑距离矩阵。
(2)通过用字符串b中的元素与字符串a中的字符一次进行对比，然后对dis[i][j]进行更新。
a[j-1]==b[i-1]时，eq=0；
a[j-1]!=b[i-1]时，eq=1；
dis[i][j]=min(dis[i-1][j]+1,dis[i][j-1]+1,dis[i-1][j-1]+eq);
(3)最终结果为dis[n][m];

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void){
    char a[500],b[500];
    int i,j,eq;
    while(scanf("%s %s",a,b)!=EOF){
        int m=strlen(a);
        int n=strlen(b);
        int dis[n+1][m+1];
        for(i=0;i<=m;i++){
            dis[0][i]=i;
        }
        for(i=0;i<=n;i++){
            dis[i][0]=i;
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                if(b[i-1]==a[j-1]){
                    eq=0;
                }else{
                    eq=1;
                }
                int min=dis[i-1][j]+1;
                if(min>dis[i][j-1]+1){
                    min=dis[i][j-1]+1;
                } 
                if(min>dis[i-1][j-1]+eq){
                    min=dis[i-1][j-1]+eq;
                }
                dis[i][j]=min;
            }
        }
        printf("%d\n",dis[n][m]);
    }
    return 0;
}