Edit Distance（编辑距离）算法。计算两个字符串的类似程度。
最近须要作两个字符串的类似度比较，涉及到了这个算法，因而写一篇博客记录一下。算法
算法简介
Edit Distance 算法，又称Levenshtein Distance(LD)算法，如下简称LD,LD 能够衡量两字符串的类似性。数组
距离的概念
算法里主要涉及的就是一个距离的概念（名字里带的就是。。）
距离，就是对于当前的两个字符串，要从
一个字符串转换成另外一个字符串的过程当中的添加、删除、修改的次数。
好比:
string_1 = "abc";
string_2 = "abd";
则，从string_1 转换到string_2 只须要 把 字符‘c’，转换成字符 'd'就好了，这只须要一次修改。
因而string_1 到string_2 的距离是 1。
显然，当两个字符串的距离越大，这两个字符串的类似度就越低。
算法的思路
先求出这两个字符串的长度。
int m = string_1.length();
int n = string_2.length();
显然，若 m，n中有一个是0，就不用比了，返回另外一个的长度就好了。（显然这就是距离了）。
若都不是0，那么，须要计算string_1 到string_2 须要修改多少遍了。因而，为了计算方便，
初始化一个 (M+1)*(N+1)的矩阵来存 int[][] different = new int[m+1][n+1];
注意，这个时候，为了高效计算，须要将 different 数组的第一行 也就是different[i][0]和第一列也就是different[0][i] 随i，从0开始递增。
接下来就是处理字符串了。 从头开始扫描这两个字符串，用 i，j来分别表示扫描到了string_1 和string_2的位置。
这时候，须要一个临时变量来记录 两个字符串中的某一位置的字符时候同样。
int temp = 1;// 1表示不一样，0，表示相同。
显然：
接下来就是关键了：
咱们须要从 different [i-1][j]+1, different [i][j-1]+1,和 different[i-1][j-1]+temp 中选一个最小的将它的值赋给different [i][j];
扫描完以后，咱们就能够来计算这两个字符串的类似度了。显然，它们最大的距离就是 这两个字符串的长度的大的那个长度。
资料显示，通常，将两个字符串的类似度定义为： 1-它们的距离/这两个字符串长度的最大值
算法实现
mfc中Edit Distance算法的实现