【51Nod】1006 - 最长公共子序列Lcs（LCS）

FishWang

发布于 2025-08-27 10:01:57

12000

代码可运行

运行总次数：0

代码可运行

点击打开题目

1006 最长公共子序列Lcs

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

关注

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：

abcicba

abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Input

第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

Output

输出最长的子序列，如果有多个，随意输出1个。

Input示例

abcicba
abdkscab

Output示例

abca

模板题。

代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
char a[1011];
char b[1011];
int dp[1011][1011];
int d[1011][1011];		//记录dp从哪里推出 
int l1,l2;
void LCS()
{
	for (int i = 1 ; i <= l1 ; i++)
	{
		for (int j = 1 ; j <= l2 ; j++)
		{
			if (a[i-1] == b[j-1])		//下标从0开始的
			{
				dp[i][j] = dp[i-1][j-1] + 1;
				d[i][j] = 0;		//从左上方得到 
			}
			else if (dp[i][j-1] >= dp[i-1][j])
			{
				dp[i][j] = dp[i][j-1];
				d[i][j] = 1;		//从左方得到 
			}
			else
			{
				dp[i][j] = dp[i-1][j];		//从上方得到
				d[i][j] = -1;
			}
		}
	}
}
void printLCS(int x,int y)
{
	if (x == 0 || y == 0)		//递归终止条件
		return;
	if (d[x][y] == 0)
	{
		printLCS(x-1 , y-1);
		printf ("%c",a[x-1]);
	}
	else if (d[x][y] == 1)
		printLCS(x , y-1);
	else
		printLCS(x-1 , y);
}
int main()
{
	scanf ("%s%s",a,b);
	l1 = strlen(a);
	l2 = strlen(b);
	LCS();
	printLCS(l1,l2);
	puts("");
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

递归