DjvuLee

//@pku DY问题完整的LCS问题
//采用迭代的方法
//标志数组的初始化很重要,让s1,s2的下标从1开始很方便设置边界检测
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;


#define N 120
#define Left -1
#define Up 1
#define NW    0
#define fin cin
int flag[N][N];
int dir[N][N];

vector<string> s1,s2,res;
void len();
void Output(int i,int j);
int main()
{
    //ifstream fin("input.txt");
    string s;
    while(1){
        s1.clear();
        s2.clear();
        res.clear();
        while(1)
        {
            fin>>s;
            if(s=="#")
                break;
            s1.push_back(s);
        }
        while(fin>>s){
            if(s=="#")
                break;
            s2.push_back(s);
        }
        len();
        Output(s1.size(), s2.size());
        bool first=true;
        for(int i=0;i<res.size();i++)
        {
            if(first){
                first=false;
            }
            else
                cout<<" ";
            cout<<res[i];
        }
        cout<<endl;
        if(fin.eof())
            break;
    }//end while
    return 0;

}


void len()
{
    for(int i=0;i<=s1.size();i++)
        flag[i][0]=0;
    for(int j=0;j<=s2.size();j++)
        flag[0][j]=0;
    
    for(int i=1;i<=s1.size();i++)
    {
        for(int j=1;j<=s2.size();j++)
        {
            if(s1[i-1]==s2[j-1])
            {
                flag[i][j]=1+flag[i-1][j-1];
                dir[i][j]=NW;
            }
            else
            {
                flag[i][j]=max(flag[i-1][j],flag[i][j-1]);
                if(flag[i-1][j]<flag[i][j-1])
                    dir[i][j]=Left;
                else
                    dir[i][j]=Up;
            }
        }
    }
}

void Output(int i,int j)
{
    if(i==0 || j==0)
        return ;
    if(dir[i][j]==NW)
    {
        Output(i-1,j-1);
        res.push_back(s1[i-1]);
    }
    else
    {
        if(dir[i][j]==Up)
            Output(i-1,j);
        else
            Output(i,j-1);
    }
}