题目描述:
要求两字符串有差异的字符个数。例如:
aaaaabaaaaa
aaaaacaabaa
这两个字符串,最大公共字串长度是5,但它们只有两个字符不同,函数输出值应为2。
如果是:
aaabbbcccddd
aaaeeeddd
函数的输出值应该是6。
比较形象地形容一下,把两个字符串排成上下两行,每个字符串都可以在任何位置插入空格以便上下对齐,每个列上至少有一个字符来自这两个字符串。当对齐程度最高的时候,没有对上的列的数即为函数输出值。
aaabbbcccddd
aaaeeeddd
最优对齐状态是:
aaabbbcccddd
aaaeee ddd
没有对上的列是6,函数输出值为6。
如果是:
abcde
acefg
最优对齐状态是:
abcde
a c efg
没有对上的列数是4,函数输出值为4。
问题抽象归类:(编辑距离问题)
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:
(1)删除一个字符;
(2)插入一个字符;
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。
要求:
输入:第1行是字符串A,第2行是字符串B。
输出:字符串A和B的编辑距离d(A,B)
思路:动态规划
开一个二维数组d[i][j]来记录a0-ai与b0-bj之间的编辑距离,要递推时,需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销,从中找出一个最小的开销即为所求
具体算法:
首先给定第一行和第一列,然后,每个值d[i,j]这样计算:d[i][j] = min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+(s1[i] == s2[j]?0:1));
最后一行,最后一列的那个值就是最小编辑距离
分享到:
相关推荐
利用动态规划算法解决编辑距离,在度量空间中有编辑距离这一个概念,通常利用动态规划等算法进行解决
主要介绍了Java动态规划之编辑距离问题示例代码,具有一定参考价值,需要的朋友可以了解下。
算法设计动态规划(编辑距离).doc
用动态规划法解决最短编辑距离问题的完整代码,可以直接运行,有注释。
动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar
如果是A串的第i个字符和B串的第j个字符 1.在A的第i个字符后插入一个字符B[j],问题转化为计算A[i...lenA]和B[j+1...lenB]的距离 ...d [i-1][j] 、d [i][j-1]、d [i-1][j-1]进行比较,其中最小的就是当前A和B的编辑距离
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和B,编程计算其编辑距离d...
算法设计动态规划(编辑距离).doc
详细说明:此算法也是非常常用的算法之一,在这个算法中我们特别要明白编辑距离问题的实质所在.
试验题目:近似字符串匹配问题计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质: 1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1; 2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==...
1、 掌握动态规划算法的基本步骤:找出最优解的性质,并刻画其结构特征;递归地定义最优值;以自底向上的方式计算出最优值;根据计算最优值时得到的信息,构造最优解。 求X和Y的最长公共子序列长度以及最长公共子...
用动态规划实现最短编辑距离的求解.cpp
应用动态规划来解决编辑距离,算法设计中动态规划习题2
输入任意两个字符串,计算它们的编辑距离。 编辑距离是指两个字符串之间,由一个转换为另一个所需的最少编辑操作次数。许可的编辑操作包括字符的替换、插入和删除。
这个算法其实是一个动态规划(DP)。levenshtein() 返回两个字符串之间的 Levenshtein 距离。 Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作...
编辑距离的动态规划实现,C/C++,直接可以使用,设:A字符串为a[0:m-1],B字符串为b[0:n-1]; d[i][j]表示a[0]到a[i]变化为b[0]b[j]的编辑距离; 则有: {█(d[i][j]=d[i-1]d[j-1],a[i]=b[j]@min┬█(0≤i≤m-1,@0≤j...
利用动态规划计算编辑距离,其模型如下: 对于两个字符串a和b,计算两个字符串的相似度,即计算两个字符串的编辑距离,相当于计算它们字串的编辑距离,再加上从子串到全串所需的最少编辑次数即可,不断地进行递推。 ...
动态规划 编辑距离 可以用来判别字符串的差异