Palindromic Subsequence

A Subsequence is a sequence obtained by deleting zero or more characters in a string. A Palindrome is a string which when read from left to right, reads same as when read from right to left. Given a string, find
the longest palindromic subsequence. If there are many answers to it, print the one that comes lexicographically earliest.

Constraints

• Maximum length of string is 1000.
• Each string has characters `a' to `z' only.

Input 

Input consists of several strings, each in a separate line. Input is terminated by EOF.

Output 

For each line in the input, print the output in a single line.

Sample Input 

aabbaabb
computer
abzla
samhita

Sample Output 

aabbaa
c
aba
aha

/*
 * Author:  ******
 * Created Time:  2013/10/4 19:02:21
 * File Name: A.cpp
 * solve: A.cpp
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<iostream>
#include<vector>
#include<queue>
//ios_base::sync_with_stdio(false);
//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define sz(v) ((int)(v).size())
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clr(x) memset(x,0,sizeof(x))
#define clrs( x , y ) memset(x,y,sizeof(x))
#define out(x) printf(#x" %d\n", x)
#define sqr(x) ((x) * (x))
typedef long long LL;

const int INF = 1000000000;
const double eps = 1e-8;
const int maxn = 1100;

int sgn(const double &x) {  return (x > eps) - (x < -eps); }

char in1[maxn];
char in2[maxn];

struct node
{
    string str;
    int len;
}dp[maxn][maxn];
int main() 
{
    //freopen("in.txt","r",stdin);
    while(scanf("%s",in1 + 1) == 1)
    {
        int len = strlen(in1+1);

        repf(i,1,len)
            in2[i] = in1[len - i + 1];

        repf(i,0,len)
        {
            dp[0][i].len = 0;
            dp[0][i].str = "";
            dp[i][0].len = 0;
            dp[i][0].str = "";
        }


        repf(i,1,len)
            repf(j,1,len)
            {
                if(in1[i] == in2[j])
                {
                    dp[i][j].len = dp[i-1][j-1].len + 1;
                    dp[i][j].str = dp[i-1][j-1].str +  in1[i];
                }else
                {
                    if(dp[i-1][j].len > dp[i][j-1].len)
                    {
                        dp[i][j].len = dp[i-1][j].len;
                        dp[i][j].str = dp[i-1][j].str;
                    }else if(dp[i-1][j].len < dp[i][j-1].len)
                    {
                        dp[i][j].len = dp[i][j-1].len;
                        dp[i][j].str = dp[i][j-1].str;
                    }else
                    {
                        dp[i][j].len = dp[i-1][j].len;
                        dp[i][j].str = min(dp[i-1][j].str,dp[i][j-1].str);
                    }
                }
            }

        //cout<<dp[len][len].str<<endl;
        //int len1 = dp[len][len].len;//str.length();
        //rep(i,0,len1)
        //  cout<<dp[len][len].str[i];
        //cout<<endl;
        
        int Len = dp[len][len].len;
        string ans = dp[len][len].str;//得到的这个str不一定是回文串！！！！！
        
        if(Len%2)
        {
            rep(i,0,Len/2)
                cout<<ans[i];
            repd(i,Len/2,0)
                cout<<ans[i];
            cout<<endl;
        }else
        {
            rep(i,0,Len/2)
                cout<<ans[i];
            repd(i,Len/2-1,0)
                cout<<ans[i];
            cout<<endl;
        }
    }
    return 0;
}