LCS变形--hdu1503

题目其实很简单，就是你找到两个字符串的最大公共子序列，然后把两个字符串都输入，但是最大公共子序列只输出一次

这道题初看其实很难理解，搞明白了之后我画了一张图，有了它这道题小学生都能做出来啦！

比方说你已经找到了图中的黑线连接的关系（最大公共子序列），那么已按照图中的圆圈圈起来的顺序输出这些字符就好啦~

思路清楚之后，核心还是LCS算法，多了一点就是要储存LCS，如何储存呢？不用我多讲，请看代码：

#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;

const int maxn=0x3f3f3f3f;
char a[110],b[100]; 
int dp[110][110];
int la,lb;
int len;

struct node{
    int ba;
    int bb;
    char c;
}ans[110];

void lcs(){
    for(int i=1;i<=la;i++){
        for(int j=1;j<=lb;j++){
            if(a[i]==b[j]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        }
    }
    if(!dp[la][lb]) printf("%s%s",a,b);
    else{
        int i=la;
        int j=lb;
        len=1;
        while(i!=0 && j!=0){
            if(a[i]==b[j] && (dp[i][j]==dp[i-1][j-1]+1)){
                ans[len].ba=i;
                ans[len].bb=j;
                ans[len++].c=a[i];
                i--;
                j--; 
            }
            else if(dp[i][j-1]>dp[i-1][j]){
                j--;
            }
            else{
                i--;
            }
        }
    }
}

int main()
{
//    freopen("in.txt","r",stdin);
    while( scanf("%s%s",a+1,b+1) ){
        memset(dp,0,sizeof(dp));
        if(a[1]=='0') break;
        la=strlen(a+1);
        lb=strlen(b+1);
        lcs();
        
        int i=1;
        int j=1;
        for(int k=len-1;k>0;k--){
            while(i < ans[k].ba){
                cout<<a[i];
                i++;
            }
            while(j < ans[k].bb){
                cout<<b[j];
                j++;
            }
            cout<<ans[k].c;
            i++;
            j++;        
        }
        printf("%s%s
",a+1+ans[1].ba,b+1+ans[1].bb);
    }
    return 0;
}