最长公共子序列
英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的
应用
最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。
动态规划
第一步：先计算最长公共子序列的长度。
第二步：根据长度，然后通过回溯求出最长公共子序列。
现有两个序列X={x1,x2,x3，...xi}，Y={y1,y2,y3，....，yi}，
设一个C[i,j]: 保存Xi与Yj的LCS的长度。
递推方程为：
代码亲测:
#include <bits/stdc++.h>
const int MAX=;
char x[MAX];
char y[MAX];
int DP[MAX][MAX];
int b[MAX][MAX];
using namespace std; int PRINT_LCS(int b[][MAX],char *x,int i,int j)
{
if(i==||j==)
return ;
if(b[i][j]==)
{
PRINT_LCS(b,x,i-,j-);
cout<<x[i]<<" ";
}
else if(b[i][j]==)
{
PRINT_LCS(b,x,i-,j);
}
else if(b[i][j]==)
{
PRINT_LCS(b,x,i,j-);
} }
int main()
{
int T;
int n,m,i,j;
cin>>T;
while(T--)
{
while(cin>>n>>m)
{
for(int i=; i<=n; i++)
cin>>x[i];
for(int j=; j<=m; j++)
cin>>y[j];
memset(DP,,sizeof(DP));
for(i=; i<=n; i++)
{
for(j=; j<=m; j++)
{
if(x[i]==y[j])
{
DP[i][j]=DP[i-][j-]+;
b[i][j]=;
} else if(DP[i-][j]>=DP[i][j-])
{
DP[i][j]=DP[i-][j];
b[i][j]=;
}
else
{
DP[i][j]=DP[i][j-];//Max(DP[i-1][j],DP[i][j-1]);
b[i][j]=;
}
}
}
cout<<DP[n][m]<<endl;
PRINT_LCS(b,x,n,m);
cout<<endl;
}
}
return ;
}