返回两个字符串最长公共子序列.

1，解决:一个简单的动态规划:
string a,b;
dp[0][_] = dp[_][0] = 0;
dp[i][j] = a[i]==b[j]?   dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);

2，实例代码:

#include<iostream>
using namespace std;

const int N=100;
int dp[N][N];

//该函数只是得到最大公共长度
int maxSubSquence(const char* a,const char* b)
{
    memset(dp,0,sizeof(dp));
    int m=strlen(a);
    int n=strlen(b);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
                dp[i][j]=dp[i-1][j]>dp[i][j-1]? dp[i-1][j]:dp[i][j-1];
        }
    return dp[m][n];
}


//可以将最长序列返回
char re[N];
int maxSubSquence2(const char* a,const char* b)
{
    int s[N][N];
    memset(dp,0,sizeof(dp));
    int m=strlen(a);
    int n=strlen(b);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                s[i][j]=1;
            }
            else
                dp[i][j]=dp[i-1][j]>dp[i][j-1]? (s[i][j]=2,dp[i-1][j]):(s[i][j]=3,dp[i][j-1]);
        }
    int len=dp[m][n];
    re[len]='\0';
    //根据s[i][j]的状态提取公共子序列
    for(int i=m,j=n;i>0&&j>0;)
    {
        switch(s[i][j])
        {
        case 1:
            re[--len]=a[i-1];i--;j--;
            break;
        case 2:
            i--;
            break;
        case 3:
            j--;
            break;
        }
    }
    return dp[m][n];
}

int main()
{
    const char* a="xyxzyxyzzy";
    const char* b="xzyzxyzxyzxy";
    cout<<maxSubSquence2(a,b)<<endl;
    cout<<re<<endl;
    return 0;
}