mahmoud-a
8/25/2017 - 5:07 PM

## https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=472

``````#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 105;
const int OO = 1e9;

int n=0, m=0;

string t1[MAX], t2[MAX];
int cache[MAX][MAX];

int lcs(int i, int j) {
if(i == n || j == m)
return 0;

int &ret = cache[i][j];
if(ret != -1)
return ret;
ret = -1*OO;
int ch0 = -1*OO;
if(t1[i] == t2[j])
ch0 = 1+lcs(i+1, j+1);
int ch1 = lcs(i+1, j);
int ch2 = lcs(i, j+1);

return ret = max(ch1, max(ch0, ch2));
}

bool isFirst = true;

void traceOperations(int i, int j) {
if(i==n || j == m)
return;

int ch0 = -1*OO;
if(t1[i] == t2[j])
ch0 = 1+lcs(i+1, j+1);
int ch1 = lcs(i+1, j);
int ch2 = lcs(i, j+1);

int opt = lcs(i, j);
if(opt == ch0) {
if(isFirst) {
cout << t1[i];
isFirst = 0;
}
else
cout << " " << t1[i];
traceOperations(i+1, j+1);
} else if(opt == ch1) {
traceOperations(i+1, j);
} else {
traceOperations(i, j+1);
}

}

int main() {
string s1, s2;
while(cin>>s1) {
clr(cache, -1);
n = m = 0;
isFirst = true;
while(s1 != "#") {
t1[n] = s1;
n++;
cin>>s1;
}
cin>>s1;
while(s1 != "#") {
t2[m] = s1;
m++;
cin>>s1;
}
int sol = lcs(0, 0);
traceOperations(0, 0);
cout << endl;
}

/*lp(k, n) {
cout << "t1: " << t1[k] << endl;
}

lp(k, m) {
cout << "t2: " << t2[k] << endl;
}*/
return 0;
}
``````