最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的.

最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int dp[1005][1005];
//第一个字符串中的前i个位置与第二个字符串中的前j个位置构成的最长长度
//状态转移方程
//dp[i][j]=dp[i-1][j-1]+1               (s1[i]==s2[j])
//dp[i][j]=max(dp[i-1][j],dp[i][j-1])   (s1[i]!=s2[j])
int main()
{
    cin>>s1>>s2;
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=s1.size(); i++)
    {
        for(int j=1; j<=s2.size(); j++)
        {
            if(s1[i]==s2[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[s1.size()][s2.size()]<<endl;

    for(int i=s1.size(),j=s2.size();i>=1&&j>=1;){//反向输出路径
        if(s1[i-1]==s2[j-1]){
            cout<<s1[i-1]<<" ";
            i--;j--;
        }
        else {
            if(dp[i-1][j]<dp[i][j-1])
                j--;
            else i--;
        }
    }
    return 0;
}