C语言网奉行“学练同步，知行合一”的学习理念，希望大家都能理论与动手一起加强！拒绝理论派！
每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
请坚信你所喜爱的事物！
通知：举办比赛权限已经完全开放，支持老师、个人随时抽题创建校内赛等比赛，达到P2级即可
因比赛为公共资源，比赛名称建议包含学校/组织名称具有辨识度，比赛名称、公告不文雅、灌水将被删除比赛并取消权限！
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
申请优质题解的标准第一，代码格式工整整齐，第二，不少于300字的思路讲解，有配图更佳！
代码格式工整、有详细说明和配图的题解才有更多的浏览哦
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！
个人资料中有关于自己联系地址、联系电话的信息，用于我们邮寄奖品福利等，且信息不会公开，别人看不到，请大家知晓！
注意，恶意创建比赛、直接复制代码发布无营养题解的行为，将被禁止相应权限！并扣除经验值! 申请恢复请联系管理员解除
本站题解请在题目内页-我要写题解发布，这样可以出现在题目题解列表页，还可以申请加优增加曝光哦！

咖啡

用户名：Tianxn

访问量：58274

签　名：

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

等　　级
排　　名	10
经　　验	15651
参赛次数	2
文章发表	184
年　　龄	22
在职情况	学生
学　　校	西安航空学院
专　　业	软件工程

　　自我简介：

TA的其他文章

[信息学奥赛一本通-T1309]回文数-题解（C++代码）
浏览：44

[信息学奥赛一本通-T1255]迷宫问题-题解（C++代码）BFS求最短路
浏览：62

[信息学奥赛一本通-T1255]迷宫问题-题解（C++代码）DFS求最短路
浏览：34

你可能喜欢

【C语言训练】计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）
浏览：710

C语言程序设计教程（第三版）课后习题5.7 （C++代码）
浏览：501

整除问题（C语言代码）
浏览：598

不容易系列2 （C语言代码）
浏览：447

C二级辅导-进制转换（C语言代码）
浏览：387

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

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

原题链接：[信息学奥赛一本通-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金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

　　评论区

精彩推荐

【回文数(二)】（C语言代码）浏览：676

C二级辅导-公约公倍（C语言代码）浏览：1275

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）浏览：374

A+B for Input-Output Practice (VII) （C++代码）浏览：502

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）浏览：530

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）浏览：428

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）浏览：1064

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）浏览：759

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）浏览：687

printf基础练习2 （C语言代码）浏览：600