基准时间限制：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<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define maxn 1005
#define maxm 10005
#define INF 0x3f3f3f3f
#define LL long long
using namespace std; int n,m,t;
char a[maxn],b[maxn];
int c[maxn][maxn];
int dp[maxn][maxn]; void LCS(int n, int m)
{
for(int i=; i<=n; i++){
for(int j=; j<=m; j++){
if(a[i-] == b[j-]){
dp[i][j] = dp[i-][j-]+;
c[i][j] = ;
}
else if(dp[i-][j] > dp[i][j-]){
dp[i][j] = dp[i-][j];
c[i][j] = ;
}
else{
dp[i][j] = dp[i][j-];
c[i][j] = ;
}
}
}
} void dfs(int i,int j)
{
if(!i||!j) return ;
if(c[i][j]==){
dfs(i-,j-);
printf("%c",a[i-]);
}
else if(c[i][j]==)
dfs(i-,j);
else
dfs(i,j-);
} int main()
{
cin>>a>>b; memset(c,,sizeof(c));
memset(dp,,sizeof(dp)); n=strlen(a);
m=strlen(b); LCS(n,m);
dfs(n,m);
cout<<endl;
return ;
}
1~n ： 递归打印
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define maxn 1005
#define maxm 10005
#define INF 0x3f3f3f3f
#define LL long long
using namespace std; int i,j;
char a[maxn];
char b[maxn];
int dp[maxn][maxn]; void LCS(int n, int m)
{
for(int i=; i<=n; i++){
for(int j=; j<=m; j++){
if(a[i-] == b[j-])
dp[i][j] = dp[i-][j-]+; else if(dp[i][j-] > dp[i-][j])
dp[i][j] = dp[i][j-];
else
dp[i][j] = dp[i-][j];
}
}
} int main()
{
scanf("%s%s",a,b); int n=strlen(a);
int m=strlen(b); LCS(n,m); int i=n;
int j=m;
int k=dp[i][j]; //倒着来
char path[maxn]={'\0'}; //逆序
while(i && j)
{
if(a[i-] == b[j-] && dp[i][j] == dp[i-][j-]+)
{
path[--k]=a[i-];//逆序
i--;
j--;
}
else if(a[i-]!=b[j-] && dp[i-][j] > dp[i][j-])
i--;
else j--;
}
printf("%s\n",path);
return ;
}
1~n : 循环打印
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<stack>
#define maxn 1005
#define maxm 10005
#define INF 0x3f3f3f3f
#define LL long long
using namespace std; int i,j;
char a[maxn];
char b[maxn];
int dp[maxn][maxn]; //void LCS(int n, int m)
//{
// for(int i=1; i<=n; i++){
// for(int j=1; j<=m; j++){
// if(a[i-1] == b[j-1])
// dp[i][j] = dp[i-1][j-1]+1;
//
// else if(dp[i][j-1] > dp[i-1][j])
// dp[i][j] = dp[i][j-1];
// else
// dp[i][j] = dp[i-1][j];
// }
// }
//} int main()
{
scanf("%s%s",a,b);
int n=strlen(a);
int m=strlen(b);
memset(dp,,sizeof(dp)); for(int i=; i<=n; i++){
for(int j=; j<=m; j++){
if(a[i-] == b[j-])
dp[i][j] = dp[i-][j-]+;
else
dp[i][j] = max(dp[i-][j],dp[i][j-]);
}
}
int i=n;
int j=m;
int k=dp[i][j];
stack<char> s;
while(k)
{
if(a[i-] == b[j-]){
s.push(a[i-]);
i--,j--;
k--;
}
else{
if(dp[i][j] == dp[i-][j]) i--;
else j--;
}
}
while(!s.empty())
{
cout<<s.top();
s.pop();
}
return ;
}
/*
abcicba
abdkscab
*/
1~n ：栈打印