2025年最大公共字符串，最大公共子序列，编辑距离，myers等算法

大家好，我是讯享网，很高兴认识大家。

1 前言

这个4个算法比较相似，并且有以下相同点和不同点

2 异同点

以str1 = "ABCDEF" , str2="ZABCDZE" 为例

相同点:

1、都是在字符串上得到某个目标；2、算法的核心都是动态规划的思想。

不同点:

1、目标不同，其中最大公共字符串是最大连续的子序列，例如：最大公共字符串是"ABCD" ，长度为4。而最大公共子序列是"ABCDE"，长度为5。

2、编辑距离，是求从一个字符串str1到另一个字符串str2的变动的最小次数，其中变动只在一个字符串上发生，变动包括三个动作：删除，插入，更改。

3、Myers可能听得比较少，但是作为程序员应该都用过，因为SVN和GIT的版本比对算法，diff是用的这个算法，他可以比较全面的寻找到每一个节点的异同。虽然是动态规划，但是它跟前面的三个算法的遍历方式不同，这也是本质的不同，这里提一下，后面详述。补充一句，对于

不废话了，下面来直接看这三个的实现过程。

3 最大公共字符串(LCS)

最大公共字符串是最大的连续的公共的字符串的长度，既然是动态规划，必然是要有递推式。先写出来。

以str1 = "ABCDEF" , str2="ZABCDZE" 为例， $lcs_{i,j}$
讯享网为 str1[0:i+1] 和 str2[0:j+1] 的最大公共字符串。则递推如下:

下面开始写代码

def longer_common_string(str1, str2): """ 最大公共字符串 实现 """ len1 = len(str1) len2 = len(str2) max_lcs_len = 0 max_len_axis = (0, 0) lcs_matrix = [[0 for j in range(len2+1)] for i in range(len1+1)] for i, char_1 in enumerate(str1): for j, char_2 in enumerate(str2): if char_1 == char_2: lcs_matrix[i+1][j+1] = lcs_matrix[i][j] + 1 if lcs_matrix[i+1][j+1] > max_lcs_len: max_lcs_len = lcs_matrix[i+1][j+1] max_len_axis = (i, j) else: lcs_matrix[i+1][j+1] = 0 return max_lcs_len, max_len_axis str1 = "ABCDEF" str2 = "ZABCDZE" lcs_len, axis = longer_common_string(str1, str2) print(lcs_len) print(axis) # print result # 4 # (3, 4)

讯享网

得到结果 lcs_len = 4, axis =（3,4），表示最大公共子序列在str1 索引为3的位置结束，在str2索引为4的地方结束。

4 最大公共子序列(LCQ)

子序列可以是非连续的字符串，因此 lcq >= lcs 恒成立。对于递推关系，则要所有改变了，以str1 = "ABCDEF" , str2="ZABCDZE" 为例， $lcs_{i,j}$ 为 str1[0:i+1] 和 str2[0:j+1] 的最大公共字符串。则递推如下:

下面开始写代码

讯享网def longer_common_sequence(str1, str2): """ 最大公共子序列 实现 """ len1 = len(str1) len2 = len(str2) max_lcq_len = 0 max_len_axis = (0, 0) lcq_matrix = [[0 for j in range(len2+1)] for i in range(len1+1)] for i, char_1 in enumerate(str1): for j, char_2 in enumerate(str2): if char_1 == char_2: lcq_matrix[i+1][j+1] = lcq_matrix[i][j] + 1 if lcq_matrix[i+1][j+1] > max_lcq_len: max_lcq_len = lcq_matrix[i+1][j+1] max_len_axis = (i, j) else: lcq_matrix[i+1][j+1] = max(lcq_matrix[i+1][j], lcq_matrix[i][j+1]) return max_lcq_len, max_len_axis str1 = "ABCDEF" str2 = "ZABCDZE" lcq_len, axis = longer_common_sequence(str1, str2) print(lcq_len) print(axis) # print result # 5 # (4, 6)

结果意思与LCS相同，不再赘述。

5 编辑距离Edit Distance

目标：使得str1通过替换、插入，删除三种操作，以最小的操作数，变为str2

编辑距离与LCS，LCQ不同之处在在于，编辑距离是找不同，前两者是找相同，在某种意义上也是殊途同归。

先上递推公式，再解释

ED代表编辑距离, $ED_{i,j}$ 表示 str1[:i] 和 str2[:j] 的编辑距离。下面来一行一行的解释：

5.1 0==min(i,j)

初始化，当i为0，或者j为0时，编辑距离就等于i和j中的最大值。

5.1.1 当 min(i,i)==0 ，必然有一个为空字符串，假设 i==0 ，那么自然,从空字符串到 str2[:j] 需要次插入操作

5.2 Others

当 i不等于0且j不等于0时，选取三种操作替换、删除完成我们目标

5.2.1 $ED_{i-1,j-1}+d (d=0 if str1[i] == str2[j] else 1)$ 这里说的是替换，用 str2[j]替换str1[i]时。而当str1[i]==str2[j]时，是不需要替换的，所以此时d=0。

5.2.2 $ED_{i-1,j}+1$ ， $ED_{i,j}$ 相对于 $ED_{i-1,j}$ 多了一个str1[i]，对应的操作是删除。

5.2.2 $ED_{i,j-1}+1$ ， $ED_{i,j}$ 相对于 $ED_{i,j-1}$ ，少了一个str2[j]，对应操作是增加。

最后再从增加，删除，插入三个操作中取得最小值。

代码如下：

def edit_distance(str1, str2): len1 = len(str1) len2 = len(str2) ed_matrix = [[max(i, j) if 0 == min(i,j) else 0 for j in range(len2+1)] for i in range(len1+1)] for i, char_1 in enumerate(str1): for j, char_2 in enumerate(str2): if char_1 == char_2: d = 0 else: d = 1 replace_dist = ed_matrix[i][j] + d insert_dist = ed_matrix[i-1][j] + 1 delete_dist = ed_matrix[i][j-1] + 1 ed_matrix[i+1][j+1] = min(replace_dist, insert_dist, delete_dist) return ed_matrix[-1][-1] str1 = "ABCDEF" str2 = "ZABCDZE" ed = edit_distance(str1, str2) print(ed) # print # 3

终于把上面的三款砖抛完了，该引出玉了

6、Myers

6.1 遍历方式不同

上面三种的动态规划，都是以 x，y轴作为遍历方便的，而Myers是以 x+y 和 x-y的方向上做遍历的，这样有个好处，就是在碰到连续的 str1[i]==str2[j]可以以时间复杂度为1的方法，走快车道。