JAG Asia 2006 Problem F: It Prefokery Pio

gistfile1.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define RALL(a) (a).rbegin(),(a).rend()
typedef vector<int> vi;
typedef vector<vi> vvi;

string reverseLcs(string & a, string & b, vvi & dp, size_t i, size_t j)
{
    if (i == 0 || j == 0) {
        return "";
    }

    if (a.at(i - 1) == b.at(j - 1)) {
        return reverseLcs(a, b, dp, i - 1, j - 1) + a.at(i - 1);
    } else {
        if (dp[i - 1][j] == dp[i][j]) {
            return reverseLcs(a, b, dp, i - 1, j);
        } else {
            return reverseLcs(a, b, dp, i, j - 1);
        }
    }
}

string lcs(string & a, string & b)
{
    vvi dp(a.size() + 1, vi(b.size() + 1));

    FOR(i, 1, dp.size()) {
        FOR(j, 1, dp[0].size()) {
            if (a.at(i - 1) == b.at(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j - 1]);
            }
        }
    }

    return reverseLcs(a, b, dp, a.length(), b.length());
}

int main()
{
    string str;
    while (cin >> str) {
        string rstr(RALL(str));
        cout << lcs(str, rstr) << endl;
    }

    return 0;
}