http://www.spoj.com/problems/ADFRUITS/

main.cc

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int kSize = 101;

int main() {
#ifdef HOME
    freopen("/home/acarus/input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    string a, b;
    while (cin >> a >> b) {
        int lcs[kSize][kSize] = {};
        int parent[kSize][kSize];
        for (int i = 1; i <= a.size(); ++i) {
            for (int j = 1; j <= b.size(); ++j) {
                int c = a[i - 1] == b[j - 1] ? 1 : 0;
                if (lcs[i - 1][j - 1] + c > lcs[i][j]) {
                    lcs[i][j] = lcs[i - 1][j - 1] + c;
                    parent[i][j] = c + 1;
                }

                if (lcs[i - 1][j] > lcs[i][j]) {
                    lcs[i][j] = lcs[i - 1][j];
                    parent[i][j] = 3;
                }

                if (lcs[i][j - 1] > lcs[i][j]) {
                    lcs[i][j] = lcs[i][j - 1];
                    parent[i][j] = 4;
                }
            }
        }

        vector<int> ca, cb;
        int x = a.size(), y = b.size();
        while (x > 0 && y > 0) {
            if (parent[x][y] == 2) {
                ca.push_back(x - 1);
                cb.push_back(y - 1);
            }

            if (parent[x][y] < 3) --x, --y;
            else if (parent[x][y] == 3) --x;
            else --y;
        }

        reverse(begin(ca), end(ca));
        reverse(begin(cb), end(cb));
        string ans = "";
        x = 0, y = 0;
        for (int i = 0; i < ca.size(); ++i) {
            while (x < ca[i]) ans += a[x], ++x;
            while (y < cb[i]) ans += b[y], ++y;
            ans += a[x];
            ++x, ++y;
        }
        while (x < a.size()) ans += a[x++];
        while (y < b.size()) ans += b[y++];
        cout << ans << endl;
    }
    return 0;
}