【问题描述】

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

【输入形式】

第一行为一个整数，表示序列X的字符数
第二行依次输入序列X的字符
第三行为一个整数，表示序列Y的字符数
第四行依次输入序列Y的字符

【输出形式】

输出X和Y的最长公共子序列

【样例输入】

7
ABCBDAB
6
BDCABA

【样例输出】

BCBA

c++代码

#include<iostream>
#include<cstring>
using namespace std; 
const int maxn=100;
void LCSLength(char *x ,char *y,int m,int n, int c[][maxn], int b[][maxn])
{
       int i ,j;
       for (i = 0; i <= m; i++) c[i][0] = 0;
       for (i = 1; i <= n; i++) c[0][i] = 0;
       for (i = 1; i <= m; i++)
          for (j = 1; j <= n; j++)
          {
            if (x[i-1]==y[j-1])
            {
                 c[i][j]=c[i-1][j-1]+1;
                 b[i][j]=1;
            }
            else if (c[i-1][j]>=c[i][j-1])
            {
                 c[i][j]=c[i-1][j];
                 b[i][j]=2;
            }
            else
            {    c[i][j]=c[i][j-1];
                 b[i][j]=3;
            }
         }
}
void LCS(int i ,int j, char *x ,int b[][maxn])
{
      if (i ==0 || j==0) return;
      if (b[i][j]== 1)
      {
           LCS(i-1,j-1,x,b);
           cout<<x[i-1];
      }
      else if (b[i][j]== 2)
           LCS(i-1,j,x,b);
      else LCS(i,j-1,x,b);
}

int main(){
	int l1,l2;
	char x[maxn],y[maxn];
	int b[maxn][maxn],c[maxn][maxn];
	cin>>l1;
	for(int i=0;i<l1;i++){
		cin>>x[i];
	}
	cin>>l2;
	for(int i=0;i<l2;i++){
		cin>>y[i];
	}
	LCSLength(x,y,l1,l2,c,b);
	LCS(l1,l2,x,b);
	return 0;
}