AT_dp_f LCS

题目描述

给定一个字符串 s s s 和一个字符串 t t t ,输出 s s s t t t 的最长公共子序列。

输入格式

两行,第一行输入 s s s ,第二行输入 t t t

输出格式

输出 s s s t t t 的最长公共子序列。如果有多种答案,输出任何一个都可以。

说明/提示

数据保证 s s s t t t 仅含英文小写字母,并且 s s s t t t 的长度小于等于 3000 3000 3000

正解

Part 1

第一件事是弄清楚 LCS 是什么。

LCS 的中文是最长公共子序列,求的是长度。在这道题目中,需要我们求这个字符串到底是什么,第一步就是先求出它的长度。

老规矩:

一、状态:因为这次有两个字符串,所以要开二维数组,即 d p i j dp_{i_j} dpij。根据以前的经验, d p i j dp_{i_j} dpij 中的 i i i j j j 表示的都是结尾的下标,因为要求长度,所以 d p i j dp_{i_j} dpij 表示第一个字符串结尾下标为 i i i,第二个字符串结尾下标为 j j j,构成最长公共子序列的长度。

二、转移:因为是二维,所以二重循环遍历 i i i j j j,这里要分两种情况:

  1. s i = t j s_i=t_j si=tj 时,可以拿这个字符到最长公共子序列中,所以 d p i j = d p i − 1 j − 1 + 1 dp_{i_j}=dp_{{i-1}_{j-1}}+1 dpij=dpi1j1+1,即多了一个字符。
  2. s i ≠ t j s_i\ne t_j si=tj 时,只能以 s s s 的上一个字符或 t t t 的上一个字符为结尾,取最大值,即 d p i j = max ⁡ ( d p i − 1 j , d p i j − 1 ) dp_{i_j}=\max(dp_{{i-1}_j},dp_{i_{j-1}}) dpij=max(dpi1j,dpij1)

三、答案:因为转移中的第二小节有提到,我们没法将字符加入最长公共子序列中时,会取前面大的作为答案,所以不需要求所有答案的最大值,只需输出 d p n m dp_{n_m} dpnm 即可。

Part 2

这个时候我们只是知道最长公共子序列的长度,并不是具体的字符串,所以还需要特定的输出。

现在我们可以倒推。令 i = n , j = m i=n,j=m i=n,j=m

  1. s i = t j s_i=t_j si=tj,那么和 Part 1 第二大段的第一小节相反, i − 1 , j − 1 i-1,j-1 i1,j1,还需要更新答案: a n s d p i j = s i ( t j ) ans_{dp_{i_j}}=s_i(t_j) ansdpij=si(tj)
  2. d p i − 1 j > d p i j − 1 dp_{{i-1}_j}>dp_{i_{j-1}} dpi1j>dpij1,因为 Part 1 第二大段的第二小节中只是求最大值,所以需要进一步分析,因为 i − 1 i-1 i1 的情况比 j − 1 j-1 j1 的情况好,所以 i − 1 i-1 i1
  3. 反之, j − 1 j-1 j1

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

char a[3010],b[3010],ans[3010];
int n,m,dp[3010][3010];

void solve()
{
	cin >> a+1 >> b+1;
	n = strlen(a+1);
	m = strlen(b+1);
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			if (a[i] == b[j])
				dp[i][j] = dp[i-1][j-1]+1;
			else
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
	int i = n,j = m;
	while (dp[i][j] > 0)
		if (a[i] == b[j])
			ans[dp[i][j]] = a[i],i--,j--;
		else if (dp[i-1][j] > dp[i][j-1])
			i--;
		else
			j--;
	for (int i = 1;i <= dp[n][m];i++)
		cout << ans[i];
}

signed main()
{
	solve();
	printf("\n");
	return 0;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部