51nod 1006：最长公共子序列Lcs

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 <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

char a[1005];
char b[1005];
int dp[1005][1005];
int pre[1005][1005];

void dfs(int m,int n)
{
	if(m==0||n==0)
		return;
	if(pre[m][n]==1)
	{
		dfs(m-1,n-1);
		cout<<a[m];
	}
	else if(pre[m][n]==2)
	{
		dfs(m-1,n);
	}
	else
	{
		dfs(m,n-1);
	}

}


int main()
{
	int i,j,len1,len2;
	memset(dp,0,sizeof(dp));
	memset(pre,0,sizeof(pre));

	cin>>a+1>>b+1;

	len1=strlen(a+1);
	len2=strlen(b+1);
	
	for(i=1;i<=len1;i++)
	{
		for(j=1;j<=len2;j++)
		{
			if(a[i]==b[j])
			{
				dp[i][j]=dp[i-1][j-1]+1;
				pre[i][j]=1;
			}
			else
			{
				if(dp[i-1][j]>dp[i][j-1])
				{
					dp[i][j]=dp[i-1][j];
					pre[i][j]=2;
				}
				else
				{
					dp[i][j]=dp[i][j-1];
					pre[i][j]=3;
				}
			}
		}
	}
	dfs(len1,len2);
	cout<<endl;
	return 0;
}