资源描述：
《编辑距离问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章动态规划编辑距离问题★问题描述：设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为。★算法设计：对于给定的字符串A和字符串B，计算其编辑距离。★数据输入：输入数据的第一行是一个正整数，表示一共有几组数据。每组数据两行，每行一个字符串。*每个字符串长度不超过1000★结果输出：输出编辑距离。对于每组数据，请输出一个整数表示两个字符串的编辑距
2、离。每个答案占一行。SampleInput：SampleOutput：24david3vivianabcaabbcc分析与解答：设所给的两个字符串为A[1:m]和B[1:n]，定义一个二维数组dp[i][j]表示状态，dp[i][j]=(A[1:i],B[1:j])表示字符串A[1:m]的子串A[1:i]变换到B[1:n]的子串B[1:j]的编辑距离，即子串A[1:i]至少要经过多少次操作（插入、删除、修改）可以变为B[1:j]。单字符a,b间的编辑距离定义为例如，字符串A:AGTAAGTAGGC转换为字符串B:AGTCTGAC
3、GC。操作一：A串：AGTAAGT*AGGCB串：AGT*C*TGACGC需要5步操作（2次删除，2次修改，1次删除）操作二：A串：AGTAAGTAGGCB串：AGTCTG*ACGC需要4次操作（3次修改，1次删除）我们计算的编辑距离是变换的最小步数，所以要取其中的最小值。考察从字符串A[1:i]到字符串B[1:j]的转换，有三种情况可以导致上面设计的状态发生转移：（1）可以删除字符A[i]需要1次操作。只将字符A[i]从A串中删除，对序列B[1:j]没有任何影响，此时问题的最优子结构形式为将A[1:i-1]变为B[1:j]，再
4、加一步删除操作，可得dp[i][j]=dp[i-1][j]+1。（2）可以在A[i]后面插入一个字符ch（ch==B[j]）需要1次操作。在进行插入操作时，串A[1:i]无任何变化，在A串i+1位置上插入字符B[j],问题的最优子结构形式为将A[1:i]变为B[1:j-1],再加一步插入操作，可得dp[i][j]=dp[i][j-1]+1。（3）可以修改字符A[i]，使它变为B[j]，若A[i]=B[j]，修改其实相当于用了0步；若A[i]!=B[j]，修改相当于用了1步。所以dp[i][j]=dp[i-1][j-1]+（A[i
5、]==B[j]?0：1）。最后的dp[i][j]就是选择上述3种状态转移中的最小值。综上所述，状态转移方程dp[i][j]可归结为如下情况：(1)当两个字符相同，即A[i]=B[j]时，dp[i][j]=min{dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]}(2)当两个字符不同，即A[i]!=B[j]时，dp[i][j]=min{dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1}需要注意的是，要对dp[0][0:m]，dp[0:n][0]进行初始化。*dp[0][i
6、],就是说A串是一个空串，而B串是个长度为i的串，很显然A串变为B串就是插入i个字符，即dp[0][i]=i。*dp[i][0]，就是说A串是个长度为i的串，而B串是一个空串，很显然A串变为B串就是删除i个字符，即dp[i][0]=i。根据上述分析，编辑最短距离的算法可描述如下：intDP(char*s1,char*s2){inti,j,m=strlen(s1),n=strlen(s2),tem;//初始化for(i=0;i<=n;i++)dp[0][i]=i;//从0个字符转换为i个字符，需要插入i次一重循环时间复杂度为T(n
7、)for(i=0;i<=m;i++)dp[i][0]=i;//从i个字符转换为0个字符，需要删除i次一重循环时间复杂度为T(m)//用动态规划方法计算编辑距离for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(s1[i-1]==s2[j-1])tem=dp[i-1][j-1];//当两个字符相同时，替换操作代价为0，直接将dp[i-1][j-1]转移过来elsetem=dp[i-1][j-1]+1;//当s1[i-1]!=s2[j-1]时,替换操作代价为1tem=min(tem,dp[i][j-1]+1)
8、;//dp[i][j-1]+1为在s1的i+1位置上插入字符s2[j]tem=min(tem,dp[i-1][j]+1);//dp[i-1][j]+1为在s1的i位置上删除字符s1[i]dp[i][j]=tem;//dp[i][j]取3种状态的最小值}retur
