LCS，Longest Common Subsequenc，最长公共子序列，子序列在原序列中可以不连续，但必须先后顺序保持一致。例如ABCD中，BD是一个子序列，DB不是。

LCS常被用来计算文本相似度，其中的一种相似度计算方式：

这种计算方式的优点是可以平衡两文本长度差异，更公平。

1.dp

def lcs(s1, s2):"""定义状态：dp[i][j]表示s1前i个字符和s2前j个字符的最长公共子序列得到两种情况下的转移方程：1) s1[i-1]=s2[j-1]: 此时 dp[i][j]=dp[i-1][j-1]+12) s1[i-1]≠s2[j-1]: 此时 dp[i][j]=max(dp[i-1][j], dp[i][j-1])当i=0或j=0时，前i或前j个字符空字符串，所以最长子序列长度都为0:param s1::param s2::return:"""s1, s2 = ' ' + s1, ' ' + s2  # 添加占位符方便下标计算len_s1, len_s2 = len(s1), len(s2)dp = [[0] * len_s2] * len_s1for i in range(len_s1):for j in range(len_s2):if i * j == 0:continueif s1[i] == s2[j]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[-1][-1], dp[-1][-1] * 2 / (len_s1 + len_s2)  # 返回lcs长度和相似度if __name__ == '__main__':addr1 = '北京市海淀区西北旺路10号'addr2 = '北京海淀西北旺路附近'print(lcs(addr1, addr2))# (8, 0.64)

这种实现方式需要双重循环遍历两个序列，所以时间复杂度和空间复杂度都是O(mn)，m、n为两个序列的长度。

2.dp（单数组优化）

主要针对空间复杂度进行优化，上面实现方式构建的dp数组是m x n，可以通过下面单数组优化的方式将空间复杂度降到O(min(m, n))。

实现中以短文本的长度构建数组，外层循环遍历长文本，内层循环遍历短文本。下面代码为了方便没有做这个逻辑处理，空间复杂度是O(len(s2))。

def lcs(s1, s2):"""原来的二维数组的更新方式是从左到右，从上到下。、将这个二维数组想象成一个矩阵，每次更新一个dp[i][j]时，只参考了三个位置的值：1) dp[i-1][j-1]: 左上位置2) dp[i][j-1]: 左边位置3) dp[i-1][j]: 上方位置因此，只需要这个矩阵中j所在的数组长度就可以替代二维数组。定义dp[j]为s1与s2前j个元素的最长子序列长度，则没i轮迭代中dp[j]的值表示s1前i个字符和s2中前j个字符的最长子序列长度。因为数组是从左往右覆盖更新，因此：1) dp[j]=dp[i-1][j]    2) dp[j-1]=dp[i][j-1]此时只需要解决dp[i-1][j-1]位置的元素获取。设这个变量名left_up，每次外层循环初始为0，表示内层遍历的文本长度为0时的最长子序列长度。内层循环中，dp[j]在更新之前表示dp[i-1][j]，因此只需要在每次dp[j]更新后将更新之前的dp[j]赋值给left_up，这样在下一个j的循环中left_up其实就是dp[i-1][j-1]，也就是当前位置的左上角元素。:param s1::param s2::return:"""s1, s2 = ' ' + s1, ' ' + s2len_s1, len_s2 = len(s1), len(s2)dp = [0] * len_s2for i in range(len_s1):left_up = 0for j in range(len_s2):temp = dp[j]if i * j == 0:continueif s1[i] == s2[j]:dp[j] = left_up + 1else:dp[j] = max(dp[j - 1], dp[j])left_up = tempreturn dp[-1], dp[-1] * 2 / (len_s1 + len_s2)  # 返回lcs长度和相似度if __name__ == '__main__':addr1 = '北京市海淀区西北旺路10号'addr2 = '北京海淀西北旺路附近'print(lcs(addr1, addr2))# (8, 0.64)