题解 | #计算字符串的编辑距离#

题解与证明：levenshtein算法是正确的

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

char stri[1001],strj[1001];
int matrix[1001][1001];

int lev(int i,int j){
    if(stri[i-1]==strj[j-1])
        return matrix[i-1][j-1];
    int min=matrix[i-1][j-1];
    min=min<=matrix[i-1][j]?min:matrix[i-1][j];
    min=min<=matrix[i][j-1]?min:matrix[i][j-1];
    return min+1;
}

int main(){

    while(scanf("%s",stri)!=EOF){
        scanf("%s",strj);
        int leni=strlen(stri),lenj=strlen(strj);
        int i=0,j=0;
        while(i<=leni){
            matrix[i][0]=i;
            i++;
        }
        while(j<=lenj){
            matrix[0][j]=j;
            j++;
        }
        for(j=1;j<=lenj;j++)
            for(i=1;i<=leni;i++)
                matrix[i][j]=lev(i,j);
        printf("%d\n",matrix[leni][lenj]);
    }
}