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

1036 阅读 1 评论 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分

2 人评分

本文分类：题解列表
浏览次数：1036 次浏览
发布日期：2020-12-17 16:11:32
本文链接：https://blog.dotcpp.com/a/74593

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 1 条评论

发表评论取消回复

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

7月4号刷题记录yyyyyyyyyyyyyyyyyyy

结构体之时间设计

报数问题（约瑟夫环问题）

2998: 电影票

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复