ED.rar_编辑距离

#include<iostream> #include"String" using namespace std; int LevenshteinDistance(char s[],char t[],int sm,int tn); int min(int p,int q,int r); int main() { char ch[5] = {'h','e','l','l','o'}; char c[5] = {'w','o','r','l','d'}; int i = LevenshteinDistance(ch,c,5,5); cout<<i<<endl; return 0; } int LevenshteinDistance(char s[],char t[],int sm,int tn) { int d[6][6]; int i,j; int cost = 0; for(i=0;i<=tn;i++) { d[i][0] = i; } for(j=0;j<=sm;j++) { d[0][j] = j; } for(j=1;j<=sm;j++) for(i=1;i<=tn;i++) { if(s[i] == t[i]) { cost = 0; } else cost = 1; d[i][j] = min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost); } return d[sm][tn]; } int min(int p,int q,int r) { if(p<q) if(p<r) return p; else return r; else if(q<r) return q; else return r; }