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

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

 

 

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

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

#include 
      
       #include 
       
        #define INF 0x3f3f3f3fusing 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<