咖啡

用户名：Tianxn

访问量：138085

签　名：

十年OI一场空，不开LL见祖宗。

等　　级
排　　名	10
经　　验	27291
参赛次数	10
文章发表	197
年　　龄	22
在职情况	学生
学　　校	西安电子科技大学
专　　业	软件工程

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-删除重复元素（C语言代码）
浏览：894

蓝桥杯2013年第四届真题-核桃的数量（C语言代码）可AC
浏览：694

蓝桥杯基础练习VIP-回形取数（C语言代码）
浏览：2256

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

优质题解

信息学奥赛一本通T1265- 最长公共子序列-题解（C++代码）附一个求全部序列的题解

　　作者: 咖啡　　　　发表时间：2020-12-17 16:11:32 浏览：724　|　评论：1　

原题链接：信息学奥赛一本通T1265- 最长公共子序列

输出一个最长公共子序列并不难（网上很多相关代码），难点在于输出所有的最长公共子序列，因为 LCS 通常不唯一。总之，我们需要在动态规划表上进行回溯从dp[m][n]，即右下角的格子，开始进行判断：

如果格子dp[i][j]对应的s1[i-1] == s2[j-1]，则把这个字符放入 LCS 中，并跳入dp[i-1][j-1]中继续进行判断；

如果格子dp[i][j]对应的 s1[i-1] ≠ s2[j-1]，则比较dp[i-1][j]和dp[i][j-1]的值，跳入值较大的格子继续进行判断；

直到 i 或 j 小于等于零为止，倒序输出lcs。

如果出现dp[i-1][j]等于dp[i][j-1]的情况，说明最长公共子序列有多个，故两边都要进行回溯（这里用到递归）。

![](/image_editor_upload/20201217041035_30521.png)

```cpp
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;

string s1, s2;
int dp[1005][1005];
set<string> set_lcs;

int lcs(int m, int n) {
	for (int i = 1; i <= m; ++i) 
		for (int j = 1; j <= n; ++j) 
			if (s1[i - 1] == s2[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else 
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
	return dp[m][n];
}

void dfs(int i, int j, string lcs_str) {
	while (i > 0 && j > 0) {
		if (s1[i - 1] == s2[j - 1]) {
			lcs_str += s1[i - 1];
			--i, --j;
		} else {
			if (dp[i - 1][j] > dp[i][j - 1]) --i;
			else if (dp[i - 1][j] < dp[i][j - 1]) --j;
			else {
				dfs(i - 1, j, lcs_str);
				dfs(i, j - 1, lcs_str);
				return;
			}
		}
	}
	string tmp = lcs_str;
	reverse(tmp.begin(), tmp.end());
	set_lcs.insert(tmp);
}

int main() {
	cin >> s1 >> s2;
	cout << lcs(s1.size(), s2.size()) << endl;
	dfs(s1.size(), s2.size(), "");
	for (set<string>::iterator it = set_lcs.begin(); it != set_lcs.end(); ++it) 
		cout << *it << endl;
	return 0;
}
```
# ### ## 注意本题评测的时候注释掉第44行哦~~

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

LBD西瓜泥

2021-10-07 14:13:32

咖啡

TA的其他文章

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

信息学奥赛一本通T1265- 最长公共子序列-题解（C++代码）附一个求全部序列的题解

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

WU-格式化数据输出（C++代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C++代码）

ACM俱乐部密码

咖啡

TA的其他文章

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

信息学奥赛一本通T1265- 最长公共子序列-题解（C++代码）附一个求全部序列的题解

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

WU-格式化数据输出 （C++代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C++代码）

ACM俱乐部密码

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

WU-格式化数据输出（C++代码）

C语言考试练习题_一元二次方程（C语言代码）

C二级辅导-阶乘数列（C语言代码）