编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如将kitten一字转成sitting：

sitten （k→s）

sittin （e→i）

sitting （→g）

俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

问题：找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成编程字符串s2，操作有三种，添加一个字符，删除一个字符，修改一个字符。

第一种解决方法，递归迭代。A和B字符距离的比较只有三种情况：A添加字符（B的比较位置+1）、A删除字符（A的比较位置+1）、A替换字符（A和B的比较位置均+1）。程序如下：

/* *侯凯,2014-9-15 *功能：LD距离 */#include
     
      using namespace std;int CalTheDistance(int spos1,int spos2,int len1,int len2,char* a,char* b){    if(spos1 >=len1)    {        if(spos2>=len2)return 0;        else return (len2-spos2);    }    if(spos2>=len2)    {        return len1-spos1;    }    if(a[spos1]==b[spos2])    {        return CalTheDistance(spos1+1,spos2+1,len1,len2,a,b);    }    else    {        int d1 = CalTheDistance(spos1+1,spos2,len1,len2,a,b);        int d2 = CalTheDistance(spos1,spos2+1,len1,len2,a,b);        int d3 = CalTheDistance(spos1+1,spos2+1,len1,len2,a,b);        return min(d1,min(d2,d3))+1;    }}int main(){    char str1[] = "abe";    char str2[] = "acb";    //聚类为2    int distance = CalTheDistance(0,0,strlen(str1),strlen(str2),str1,str2);    cout<
      
       <
      
     

采用递归算法，只是理论上有效，便于理解，实际应用中会出现各种限制。一般，堆栈深度程序是设限制的。

第二种方法，动态规划的思想。首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。显然有：

if i == 0 且 j == 0，edit(i, j) = 0

if i == 0 且 j > 0，edit(i, j) = j

if i > 0 且j == 0，edit(i, j) = i

示例：比较的两个字符串为“abcd”和“bedf”，阶段与状态（i,j）矩阵：

计算下一行得到：

进而：

可得状态转移方程：若A(i)=B(j),则LD(i,j)=LD(i-1,j-1);否则LD(i,j)=min{LD(i-1,j-1),min(i-1,j),min(i,j-1)}+1。这个关系式可以从题目中直接推到得到。最终得到：

 

程序实现如下：

/* *侯凯,2014-9-15 *功能：LD距离 */#include
     
      using namespace std;int CalTheDistance(string A,string B){    int **ptr = new int*[ A.size()+ 1];    for(int i = 0; i < A.size() + 1 ;i++)    {        ptr[i] = new int[B.size() + 1];    }    for(int i=0;i
     

此时时间复杂度为O(mn)，空间复杂度亦为O(mn)，可对程序进一步改进，使空间复杂度降低为O（m），如下：

/* *侯凯,2014-9-15 *功能：LD距离 */#include
     
      using namespace std;int CalTheDistance(string A,string B){    int *ptr = new int[ B.size()+ 1];    for(int i=0;i
     

通过二维矩阵，我们不但可以得到两个字符串的编辑距离，也可以回溯得到匹配子串。

以上面为例A=abcd，B=bedf，LD(A,B)=3

他们的匹配为：

A：abcd_

B：_bedf

如上面所示，蓝色表示完全匹配，黑色表示编辑操作，_表示插入字符或者是删除字符操作。如上面所示，黑色字符有3个，表示编辑距离为3。

从右下角单元格回溯，若A_i=B_j，则回溯到左上角单元格；若a_i≠b_j，回溯到左上角、上边、左边中值最小的单元格，若有相同最小值的单元格，优先级按照左上角、上边、左边的顺序。

若回溯到左上角单元格，将A_i添加到匹配字串A，将B_j添加到匹配字串B；若回溯到上边单元格，将B_i添加到匹配字串B，将_添加到匹配字串A；若回溯到左边单元格，将_添加到匹配字串B，将A_j添加到匹配字串A；搜索晚整个匹配路径，匹配字串也就完成了。

在比较长字符串的时候，还有其他性能更好的算法。留待后文详述。