数据结构与算法题解：最长公共子序列和最长公共子串

详解Python最长公共⼦串和最长公共⼦序列的实现最长公共⼦串(The Longest Common Substring)LCS问题就是求两个字符串最长公共⼦串的问题。

解法就是⽤⼀个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1,否则为0。

然后求出对⾓线最长的1的序列，其对应的位置就是最长匹配⼦串的位置。

def find_lcsubstr(s1, s2):m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #⽣成0矩阵，为⽅便后续计算，⽐字符串长度多了⼀列mmax=0 #最长匹配的长度p=0 #最长匹配对应在s1中的最后⼀位for i in range(len(s1)):for j in range(len(s2)):if s1[i]==s2[j]:m[i+1][j+1]=m[i][j]+1if m[i+1][j+1]>mmax:mmax=m[i+1][j+1]p=i+1return s1[p-mmax:p],mmax #返回最长⼦串及其长度print find_lcsubstr('abcdfg','abdfg')运⾏得到输出：('dfg',3)最长公共⼦序列 (The Longest Common Subsequence)⼦串要求字符必须是连续的，但是⼦序列就不是这样。

最长公共⼦序列是⼀个⼗分实⽤的问题，它可以描述两段⽂字之间的“相似度”，即它们的雷同程度，从⽽能够⽤来辨别抄袭。

对⼀段⽂字进⾏修改之后，计算改动前后⽂字的最长公共⼦序列，将除此⼦序列外的部分提取出来，这种⽅法判断修改的部分，往往⼗分准确。

解法就是⽤动态回归的思想，⼀个矩阵记录两个字符串中匹配情况，若是匹配则为左上⽅的值加1，否则为左⽅和上⽅的最⼤值。

⼀个矩阵记录转移⽅向，然后根据转移⽅向，回溯找到最长⼦序列。

最长公共子序列（LCS）问题（非连续子序列）的两种解法最长公共子序列也称作最长公共子串，英文缩写是LCS（Longest Common Subsequence）。

其定义是：一个序列S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称S为已知序列的最长公共子序列。

关于子序列的定义通常有两种方式，一种是对子序列没有连续的要求，其子序列的定义就是原序列中删除若干元素后得到的序列。

另一种是对子序列有连续的要求，其子序列的定义是原序列中连续出现的若干个元素组成的序列。

求解子序列是非连续的最长公共子序列问题是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。

本文将介绍对子序列没有连续性要求的情况下如何用计算机解决最长公共子序列问题，对子序列有连续性要求的情况下如何用计算机解决最长公共子序列问题将在后续的文章中介绍。

一、动态规划法（Dynamic Programming）最长公共子序列问题应该是属于多阶段决策问题中求最优解一类的问题，凡此类问题在编制计算机程序时应优先考虑动态规划法，如果不能用动态规划法，而且也找不到其它解决方法，还可以考虑穷举法。

对于这个问题，只要能找到描述最长公共子序列的最优子结构和最优解的堆叠方式，并且保证最优子结构中的每一次最优决策都满足“无后效性”，就可以考虑用动态规划法。

使用动态规划法的关键是对问题进行分解，按照一定的规律分解成子问题（分解后的子问题还可以再分解，这是个递归的过程），通过对子问题的定义找出最优子结构中最优决策序列（对于子问题就是最有决策序列的子序列）以及最优决策序列子序列的递推关系（当然还包括递推关系的边界值）。

如果一个给定序列的子序列是在该序列中删去若干元素后得到的序列，也就意味着子序列在原序列中的位置索引（下标）保持严格递增的顺序。

例如,序列S = <B,C,D,B>是序列K = <A，B，C，B，D，A，B>的一个子序列（非连续），序列S的元素在在K中的位置索引I = [2,3,5,7]，I是一个严格递增序列。

[DataStructure]LCSs——最长公共⼦序列和最长公共⼦串1. 什么是 LCSs？ 什么是 LCSs? 好多博友看到这⼏个字母可能⽐较困惑，因为这是我⾃⼰对两个常见问题的统称，它们分别为最长公共⼦序列问题（Longest-Common-Subsequence）和最长公共⼦串（Longest-Common-Substring）问题。

这两个问题⾮常的相似，所以对不熟悉的同学来说，有时候很容易被混淆。

下⾯让我们去好好地理解⼀下两者的区别吧。

1.1 ⼦序列 vs ⼦串 ⼦序列是有序的，但不⼀定是连续，作⽤对象是序列。

例如：序列 X = <B, C, D, B> 是序列 Y = <A, B, C, B, D, A, B> 的⼦序列，对应的下标序列为 <2, 3, 5, 7>。

⼦串是有序且连续的，左右对象是字符串。

例如 a = abcd 是 c = aaabcdddd 的⼀个⼦串；但是 b = acdddd 就不是 c 的⼦串。

1.2 最长公共⼦序列 vs 最长公共⼦串 最长公共⼦序列和最长公共⼦串是常见的两种问题，虽然两者问题很相似，也均可以根据动态规划进⾏求解，但是两者的本质是不同的。

最长公共⼦序列问题是针对给出的两个序列，求两个序列最长的公共⼦序列。

最长公共⼦串问题是针对给出的两个字符串，求两个字符串最长的公共⼦串（有关字符串匹配相关算法可以转⾄博客《》）。

2. 动态规划⽅法求解LCSs 前⾯提到，动态规划⽅法均可以⽤到最长公共⼦序列和最长公共⼦串问题当中，在这⾥我们就不⼀⼀进⾏求解了。

我们以最长公共⼦序列为例，介绍⼀下如何利⽤动态规划的思想来解决 LCSs。

给定两个序列，找出在两个序列中同时出现的最长⼦序列的长度。

对于每⼀个序列⽽⾔，其均具有a m中⼦序列，因此采⽤暴⼒算法的时间复杂度是指数级的，这显然不是⼀种好的解决⽅案。

下⾯我们看⼀下，如何使⽤动态规划的思想来解决最⼤公共⼦序列问题。

C++笔试之基础08求两个字符串的最长公共子串，最长公共子序列，编辑距离(1) 找出两个字符串的最长公共子串题目：输入两个字符串，找出两个字符串中最长的公共子串。

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。

因此我们采用一个二维矩阵来存储中间结果，下面我们看这个二维数组如何构造？假设两个字符串分别是：”bab”和”caba”。

如果str[i] == str[j] 则matrix[i][j] = 1，否则matrix[i][j] = 0然后我们从矩阵中找出斜对角线最长的那个子字符串，就是最长公共子串。

即”ab”和”ba”分别为2。

我们可以简化一下，在当我们计算matrix[i][j]时，我们判断str[i] == str[j] 和matrix[i-1][j-1]。

如果str[i] == str[j]，则matrix[i][j] = matrix[i-1][j-1] + 1；否则matrix[i][j] = 0。

如下图所示：所以此时，我们只是将matrix[M][N]中，找到最大的值，即为最长公共子串。

然后我们还可以简化一下空间复杂度。

因为我们每判断一个matrix[i][j]时，实际上它只与matrix[i-1][j-1]相关。

故所以我们可以使用一维数组来保存上一次的结果。

实现代码如下：[cpp] view plain copy1.#include <cstring>2.#include <iostream>ing namespace std;4.5.int GetLongestCommonSubString(const char *pStr1, cons t char *pStr2)6.{7./* 判断参数合法性 */8.if (pStr1 == NULL || pStr2 == NULL)9.{10.return -1;11.}12.13.int n = strlen(pStr1);14.int m = strlen(pStr2);15.int longestCommonSubString = 0;16.17./* 申请辅助空间，并初始化为0 */18.int *LCS = new int[m];19.for (int i = 0; i < m; i++)20.{21.LCS[i] = 0;22.}23.24./* 不断判断pStr[i] ?= pStr[j]，然后根据不同情况来更新LCS */25.for (int i = 0; i < n; i++)26.{27.for (int j = m - 1; j >= 0; j--)28.{29.if (pStr1[i] == pStr2[j]) /* 如果pStr1[i] == pStr2[j]，LCS[j] = LCS[j-1] + 1 */30.{31.if (j == 0)32.{33.LCS[j] = 1;34.}35.else36.{37.LCS[j] = LCS[j-1] + 1;38.}39.}40.else /* 如果pStr1[i] != pStr2[j]，LCS[j] = 0 */41.{42.LCS[j] = 0;43.}44.45./* 更新最长子串的长度 */46.if (LCS[j] > longestCommonSubString)47.{48.longestCommonSubString = LCS[j];49.}50.}51.}52.53.delete LCS;54.LCS = NULL;55.56.return longestCommonSubString;57.}58.59.void Test(const char *testName, const char *pStr1, const char *pStr2, int expectedLongestCommonSubString)60.{61.cout << testName << " : ";62.if (GetLongestCommonSubString(pStr1, pStr2) == exp ectedLongestCommonSubString)63.{64.cout << "Passed." << endl;65.}66.else67.{68.cout << "Failed." << endl;69.}70.}71.72.int main()73.{74.Test("Test1", "caba", "bab", 2);75.Test("Test2", "abcd", "efg", 0);76.Test("Test3", "abcde", "abcde", 5);77.}(2) 找出两个字符串的最长公共子序列题目：输入两个字符串，求两个字符串的最长公共子序列。

[Python]最长公共⼦序列VS最长公共⼦串[动态规划]前⾔由于原微软开源的基于古⽼的perl语⾔的Rouge依赖环境实在难以搭建，遂跟着Rouge论⽂的描述⾃⾏实现。

Rouge存在N、L、S、W、SU等⼏⼤⼦评估指标。

在复现Rouge-L的函数时，便遇到了本博⽂的问题：求两串的最长公共⼦序列。

⼀参考⽂献全⽂参考均如下博⽂。

⼆最长公共⼦序列 & 最长公共⼦串的区别1、最长公共⼦序列(Longest Common Subsequence,LCS)：在字符串A和字符串B中都出现的序列，且顺序与母串保持⼀致最长的那个序列。

2、最长公共⼦串(Longest Common Substring)：相⽐LCS更加严格，序列必须连续出现，即公共的⼦字符串。

eg: csdnblog与belong，最长公共⼦序列为blog，最长公共⼦串为lo。

三程序设计与实现3.1 最长公共⼦序列def longestCommonSubsequence(seqA, seqB):"""最长公共⼦序列-----------[reference] 最长公共⼦序列与最长公共⼦串【动态规划】 https:///a515557595_xzb/article/details/88296989:param seqA::param seqB::return:"""m = len(seqA);n = len(seqB);init_unit={"len":0,"lcs":[]}dp = [[ init_unit ]*(n+1) for i in range(m+1)]; # m+1⾏, n+1列for i in range(0, m+1):for j in range(0, n+1):if i==0 or j==0:dp[i][j] = init_unit;elif seqA[i-1] == seqB[j-1]:tmp_str = copy.copy((dp[i-1][j-1])["lcs"]);tmp_str.append(seqA[i-1]);unit = {"len": (dp[i-1][j-1])["len"] + 1,"lcs": tmp_str}dp[i][j] = unit;elif seqA[i-1] != seqB[j-1]:if (dp[i-1][j])["len"] > (dp[i][j-1])["len"]: # 存储最长的信息dp[i][j] = dp[i-1][j];else:dp[i][j] = dp[i][j-1];else:pass;pass; # end inner for looppass; # end outer for loopreturn dp[m][n];print( longestCommonSubsequence("GM%$ABG", "gbndGFMABG") ) # {'len': 5, 'lcs': ['G', 'M', 'A', 'B', 'G']}print( longestCommonSubsequence(["G", "M", "%", "$", "A", "B", "G"], ["g","b", "n", "d", "G", "F", "M", "A", "B","G"] ) ); # {'len': 5, 'lcs': ['G', 'M', 'A', 'B', 'G']}3.2 最长公共⼦串def longestCommonSubstring(strA, strB):"""最长公共⼦串-----------[reference] 最长公共⼦序列与最长公共⼦串【动态规划】 https:///a515557595_xzb/article/details/88296989:param strA::param strB::return:"""m = len(strA);n = len(strB);init_unit={"len":0,"lcs":[]}dp = [[ init_unit ]*(n+1) for i in range(m+1)]; # m+1⾏, n+1列result ={"len":0, # 记录最长公共⼦串的长度"lcs": []};for i in range(0, m+1): # 考虑i为0或j为0的情况for j in range(0, n+1):if i==0 or j==0 or ( strA[i-1] != strB[j-1] ):dp[i][j] = init_unit;elif strA[i-1] == strB[j-1]:tmp_str = copy.copy((dp[i-1][j-1])["lcs"]);tmp_str.append(strA[i-1]);unit = {"len": (dp[i-1][j-1])["len"] + 1,"lcs": tmp_str}dp[i][j] = unit;if (dp[i][j])["len"] > result["len"]: # 存储最长的信息result = copy.copy( dp[i][j] );else:pass;pass; # end inner for looppass; # end outer for loopreturn result;print( longestCommonSubstring("GM%$ABG", "gbndGFMABG") ) # {'len': 3, 'lcs': ['A', 'B', 'G']}print( longestCommonSubstring(["G", "M", "%", "$", "A", "B", "G"], ["g","b", "n", "d", "G", "F", "M", "A", "B","G"] ) ); # {'len': 3, 'lcs': ['A', 'B', 'G']}四应⽤领域4.1 机器学习 > ⾃动⽂本摘要 / 机器翻译 / 机器阅读理解等任务中 > 评估指标 > Rouge-LRouge-L分类：句⼦级: 最长公共⼦序列⽂摘级: Union[多条句⼦] 最长公共⼦序列推荐博⽂:推荐论⽂: 《ROUGE: A Package for Automatic Evaluation of Summaries》。

最长公共子序列问题；最长公共子序列（Longest Common Subsequence, LCS）问题是指找到多个字符串中最长的公共子序列。

公共子序列是指这些字符串在所有字符串中都以相同的顺序出现，但不要求连续。

例如，对于字符串"ABCD"和"ACDF"，其最长公共子序列为"ACD"。

最长公共子序列问题可以通过动态规划来解决。

基本思路是使用一个二维数组dp，其中dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列的长度。

首先，初始化dp[0][j]和dp[i][0]为0，表示空字符串与任何字符串的最长公共子序列长度为0。

然后，对于每个字符A[i]和B[j]，如果A[i]等于B[j]，则dp[i][j] = dp[i-1][j-1] + 1，表示在之前的最长公共子序列长度的基础上加1。

否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示要么在字符串A的前i-1个字符和字符串B的前j个字符的最长公共子序列的基础上取得，要么在字符串A的前i个字符和字符串B的前j-1个字符的最长公共子序列的基础上取得。

最终，dp[m][n]即为所求，其中m和n分别为字符串A和字符串B的长度。

可以通过追踪dp数组来还原出最长公共子序列，具体方法是从dp[m][n]开始，如果A[i]等于B[j]，则该字符是公共字符，将其加入结果序列，然后向左上方移动，即dp[i-1][j-1]。

如果dp[i][j]等于dp[i-1][j]，则说明最长公共子序列在A中取得，向上移动，即dp[i-1][j]；如果dp[i][j]等于dp[i][j-1]，则说明最长公共子序列在B中取得，向左移动，即dp[i][j-1]。

重复上述过程，直到dp[i][j]为0。

动态规划经典——最长公共⼦序列问题（LCS）和最长公共⼦串问题⼀.最长公共⼦序列问题(LCS问题)给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共⼦序列，并返回其长度。

例如： A = "Hel lo W o rld" B = "loo p"则A与B的最长公共⼦序列为 "loo",返回的长度为3。

此处只给出动态规划的解法：定义⼦问题dp[i][j]为字符串A的第⼀个字符到第 i 个字符串和字符串B 的第⼀个字符到第 j 个字符的最长公共⼦序列，如A为“app”,B为“apple”，dp[2][3]表⽰ “ap” 和 “app” 的最长公共字串。

注意到代码中 dp 的⼤⼩为 (n + 1) x (m + 1) ，这多出来的⼀⾏和⼀列是第 0 ⾏和第 0 列，初始化为 0，表⽰空字符串和另⼀字符串的⼦串的最长公共⼦序列，例如dp[0][3]表⽰ "" 和“app” 的最长公共⼦串。

当我们要求dp[i][j]，我们要先判断A的第i个元素B的第j个元素是否相同即判断A[i - 1]和 B[j -1]是否相同，如果相同它就是dp[i-1][j-1]+ 1，相当于在两个字符串都去掉⼀个字符时的最长公共⼦序列再加 1；否则最长公共⼦序列取dp[i][j - 1] 和dp[i - 1][j]中⼤者。

所以整个问题的初始状态为：dp[i][0]=0,dp[0][j]=0相应的状态转移⽅程为：dp[i][j]=max{dp[i−1][j],dp[i][j−1]},A[i−1]!=B[j−1] dp[i−1][j−1]+1,A[i−1]==B[j−1]代码的实现如下：class LCS{public:int findLCS(string A, int n, string B, int m){if(n == 0 || m == 0)//特殊输⼊return 0;int dp[n + 1][m + 1];//定义状态数组for(int i = 0 ; i <= n; i++)//初始状态dp[i][0] = 0;for(int i = 0; i <= m; i++)dp[0][i] = 0;for(int i = 1; i <= n; i++)for(int j = 1; j<= m; j++){if(A[i - 1] == B[j - 1])//判断A的第i个字符和B的第j个字符是否相同dp[i][j] = dp[i -1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);}return dp[n][m];//最终的返回结果就是dp[n][m]}};该算法的时间复杂度为O(n*m)，空间复杂度为O(n*m)。

⽤Python计算最长公共⼦序列和最长公共⼦串1. 什么是最长公共⼦序列？什么是最长公共⼦串？1.1. 最长公共⼦序列（Longest-Common-Subsequences，LCS）最长公共⼦序列（Longest-Common-Subsequences，LCS）是⼀个在⼀个序列集合中（通常为两个序列）⽤来查找所有序列中最长⼦序列的问题。

这与查找最长公共⼦串的问题不同的地⽅是：⼦序列不需要在原序列中占⽤连续的位置。

最长公共⼦序列问题是⼀个经典的计算机科学问题，也是数据⽐较程序，⽐如Diff⼯具，和⽣物信息学应⽤的基础。

它也被⼴泛地应⽤在版本控制，⽐如Git⽤来调和⽂件之间的改变。

1.2 最长公共⼦串（Longest-Common-Substring，LCS）最长公共⼦串（Longest-Common-Substring，LCS）问题是寻找两个或多个已知字符串最长的⼦串。

此问题与最长公共⼦序列问题的区别在于⼦序列不必是连续的，⽽⼦串却必须是连续的。

2. 如何求解最长公共⼦序列?例如序列str_a=world，str_b=wordl。

序列wo是str_a和str_b的⼀个公共⼦序列，但是不是str_a和str_b的最长公共⼦序列，⼦序列word是str_a和str_b的⼀个LCS，序列worl也是。

暴⼒查找？寻找LCS的⼀种⽅法是枚举X所有的⼦序列，然后注意检查是否是Y的⼦序列，并随时记录发现的最长⼦序列。

假设X有m个元素，则X有2^m个⼦序列，指数级的时间，对长序列不实际。

2.1 基于递归的⽅法根据上边分析结果，可以写出简洁易懂的递归⽅法。

def recursive_lcs(str_a, str_b):if len(str_a) == 0 or len(str_b) == 0:return 0if str_a[0] == str_b[0]:return recursive_lcs(str_a[1:], str_b[1:]) + 1else:return max([recursive_lcs(str_a[1:], str_b), recursive_lcs(str_a, str_b[1:])])print(recursive_lcs('qweasde', 'asdzeexc'))2.2 基于⾃底向上动态规划的⽅法根据上述分析问题，动态规划递推公式也⾮常明显，可以写出动态规划代码：转载：https:///CheeseZH/p/8830482.html。

三个子串最长公共子序列嘿，大家好，今天我们来聊聊“最长公共子序列”这事儿，别急，先别被这几个字吓到。

你可能会想，啥？子序列？公共？最长？这么复杂的东西我怎么能理解呢？其实不然，放松点，咱们今天就把这个问题说得通俗易懂，让你像吃糖一样顺顺利利消化掉。

咱得搞明白什么叫“子序列”。

你可以把它想象成一串数字或者字母，比如“ABCDEF”，它的子序列就可能是“A, C, F”这种组合。

你看，顺序是没变的，只是选取了一些字符而已。

好啦，知道子序列啥意思后，接下来的问题是“公共”了。

就好像你和朋友分享你的零食，他拿了其中一部分，你拿了另一部分，结果你们俩拿到的零食有一些是相同的，这些相同的零食就可以叫做“公共零食”。

那么“公共子序列”呢？简单来说，就是你给我一个字符串，我给你一个字符串，咱们俩从中各自挑一些字符，把它们拼成一个共同的子序列。

哎呀，听起来是不是不那么难理解了？现在，我们要找的“最长公共子序列”就是在这两者之间，既然是“最长”，那肯定是选的字符最多的一个。

咱们再加个难度，假设这回不光有两个字符串，我们有三个！对！你没听错，三个！这个问题可就有点意思了，三个子串，怎么找出最长的共同部分呢？就好像三个朋友一起分享那包零食，你拿了一部分，另一个朋友拿了一部分，第三个朋友又拿了一部分，结果你们三个人中只有一部分零食是大家都能分享的。

听起来是不是有点烧脑？但其实一点也不难，就当是做一个小小的拼图，大家一起找出那个能够同时出现在三个字符串里的最长的共同片段。

想象一下，咱们有三个字符串，比如：“ABCD”、“BCDE”和“CDEF”，那么你看，它们的公共子序列能选出来什么呢？最简单的，就是那个“CDE”，没错，就是这么简单！就是你从这三个字符串里挑出来一个最长的“交集”，它不一定连续，但是顺序必须保持不变，拼起来就是最长的公共子序列。

你说简单不简单？不过，别被这点小小的“简单”给迷惑了，这个问题其实也不是轻松能解决的哦。