C语言网(Dotcpp.com)奉行“学练同步，知行合一”的学习理念，希望大家都能理论与动手一起加强！拒绝理论派！
每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
请坚信你所喜爱的事物！
举办比赛权限已经完全开放，支持老师、个人随时抽题创建校内赛等比赛，达到P2级即可
因比赛为公共资源，比赛名称建议包含学校/组织名称具有辨识度，比赛名称、公告不文雅、灌水将被删除比赛并取消权限！
世界上有10种人，一种是懂二进制的，另一种是不懂二进制的~
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！

咖啡

用户名：Tianxn

访问量：107182

签　名：

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

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

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

优质题解

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

　　作者: 咖啡　　　　发表时间：2020-12-17 16:11:32 浏览：508　|　评论：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分

1 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

　　评论区

LBD西瓜泥

2021-10-07 14:13:32 | |

咖啡

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

C语言训练-计算1977！* （C语言代码）

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

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

评论区

精彩推荐

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

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

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

矩阵乘法（C++代码）

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

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

WU-复数求和（C++代码）

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

DNA （C语言代码）

1113题解

咖啡

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

汽水瓶 （C++代码）（直接n/2就可以了）

【绝对值排序】 （C++代码）（利用两个库函数——abs()求绝对值 和 sort()快排）

C语言训练-计算1977！* （C语言代码）

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

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

评论区

精彩推荐

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

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

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

矩阵乘法 （C++代码）

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

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

WU-复数求和 （C++代码）

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

DNA （C语言代码）

1113题解

母牛的故事（C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

　　评论区

矩阵乘法（C++代码）

WU-复数求和（C++代码）