最长公共子序列（LCS）问题有两种方式定义子序列，一种是子序列不要求不连续，一种是子序列 必须连续。上一章介绍了用两种算法解决子序列不要求连续的最终公共子序列问题，本章将介绍要求 子序列必须是连续的情况下如何用算法解决最长公共子序列问题。
仍以上一章的两个字符串 “abcdea”和“aebcda”为例，如果子序列不要求连续，其最长公共子序列为“abcda”，如果子序列 要求是连续，则其最长公共子序列应为“bcd”。在这种情况下，有可能两个字符串出现多个长度相同 的公共子串，比如“askdfiryetd”和“trkdffirey”两个字符串就存在两个长度为3的公共子串，分 别是“kdf”和“fir”，因此问题的性质发生了变化，需要找出两个字符串所有可能存在公共子串的 情况，然后取最长的一个，如果有多个最长的公共子串，只取其中一个即可。
字符串 “abcdea”和“aebcda”如果都以最左端的a字符对齐，则能够匹配的最长公共子串就是“a”。但是 如果用第二个字符串的e字符对齐第一个字符串的a字符，则能够匹配的最长公共子串就是“bcd”。可 见，从两个字符串的不同位置开始对齐匹配，可以得到不同的结果，因此，本文采用的算法就是穷举 两个字符串所有可能的对齐方式，对每种对齐方式进行字符的逐个匹配，找出最长的匹配子串。
一、递归方法
首先看看递归方法。递归的方法比较简单，就是比较两个字符串的首 字符是否相等，如果相等则将其添加到已知的公共子串结尾，然后对两个字符串去掉首字符后剩下的 子串继续递归匹配。如果两个字符串的首字符不相等，则用三种对齐策略分别计算可能的最长公共子 串，然后取最长的一个与当前已知的最长公共子串比较，如果比当前已知的最长公共子串长就用计算 出的最长公共子串代替当前已知的最长公共子串。第一种策略是将第一个字符串的首字符删除，将剩 下的子串与第二个字符串继续匹配；第二种策略是将第二个字符串的首字符删除，将剩下的子串与第 一个字符串继续匹配；第三种策略是将两个字符串的首字符都删除，然后继续匹配两个字符串剩下的 子串。删除首字符相当于字符对齐移位，整个算法实现如下：
180 void RecursionLCS
(const std::string& str1, const std::string& str2, std::string& lcs)
181 {
182 if(str1.length() == 0 || str2.length() == 0)
183 return;
184
185 if(str1[0] == str2[0])
186 {
187 lcs += str1[0];
188 RecursionLCS(str1.substr(1), str2.substr(1), lcs);
189 }
190 else
191 {
192 std::string strTmp1,strTmp2,strTmp3;
193
194 RecursionLCS(str1.substr(1), str2, strTmp1);
195 RecursionLCS(str1, str2.substr(1), strTmp2);
196 RecursionLCS(str1.substr(1), str2.substr(1), strTmp3);
197 std::string strLongest = GetLongestString(strTmp1, strTmp2, strTmp3);
198 if(lcs.length() < strLongest.length())
199 lcs = strLongest;
200 }
201 }
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索递归
， 字符串
， 大量连续序列数据
， 序列
， 两个
， 数据库 连续字符
， 最长公共子序列
， 所有公共子序列
， 公共子序列
， 子匹配
， 子串
， 最长公共子串
， 最长
公共
lcs最长公共子序列、lcs算法最长公共子串、一个极值的三种解法、圆的最值问题三种解法、鲁班锁6根 三种解法，以便于您获取更多的相关知识。