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

531 - Compromise.cpp

#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;
}