hdu1503 最长公共子序列变形

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1503

题意：给出两个字符串要求输出包含两个字符串的所有字母的最短序列。注意输出的顺序不能变。//意会一下吧，我说不清=.=

思路：最长公共子序列的变形，需要记录位置。直接看代码应该就可以懂，不是很难。

click here：http://www.cnblogs.com/a-clown/p/5918080.html //hdu1159 最长公共子序列裸题。

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

#define ll long long

struct node

{

    int x,y;    ///x,y代表公共子串中的字母分别在两个子串中的位置

    char ch;    ///分别记录两个位置和字母

} ans[];

char a[],b[];

int dp[][];

char c[];

int main()

{

    while(cin>>a>>b)

    {

        int len1=strlen(a);

        int len2=strlen(b);

        memset(dp,,sizeof(dp));

        for(int i=; i<=len1; i++)

            for(int j=; j<=len2; j++)

                if(a[i-]==b[j-]) dp[i][j]=dp[i-][j-]+;

                else dp[i][j]=max(dp[i-][j],dp[i][j-]);

        if(dp[len1][len2]==)

        {

            cout<<a<<b<<endl;

            continue;

        }

        int p=len1-,q=len2-,k=;

        while(p>= && q>=)         ///注意逆序更好写

        {

            if(dp[p+][q+]==dp[p][q]+ && a[p]==b[q])

            {

                ans[k].x=p;

                ans[k].y=q;

                ans[k++].ch=a[p];

                p--;

                q--;

            }

            else if(dp[p][q+]>dp[p+][q]) p--;

            else q--;

        }

        int x=,y=;

        for(int i=k-; i>=; i--)

        {

            while(x!=ans[i].x) cout<<a[x],x++;

            while(y!=ans[i].y) cout<<b[y],y++;

            cout<<ans[i].ch;

            x++;

            y++;

        }

        cout<<a+ans[].x+<<b+ans[].y+<<endl;

    }

    return ;

}