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

咖啡

用户名：Tianxn

访问量：79110

签　名：

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

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

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

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

C二级辅导-求偶数和（C语言代码）
浏览：457

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

人见人爱A+B （C语言代码）
浏览：606

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

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