sym.cpp

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

#define long long long
#define nln '\n'

const long N = 1e3;

using namespace std;

fstream f1, f2;

inline void openf()
{
    f1.open("sym.inp", ios:: in);
    f2.open("sym.out", ios:: out);
}

inline void closef()
{
    f1.close();
    f2.close();
}

string str;

void data()
{
    f1.tie(0)->sync_with_stdio(0);
    f2.tie(0)->sync_with_stdio(0);
}

string palindrome(string str)
{
    // Dynamic planning
    long n = str.size();
    vector<vector<long>> dp(N);
    for (long i = 0; i <= n; ++i)
        dp[i].resize(n+2, 0);

    for (long i = 1; i <= n; ++i)
        for (long j = 0; j < n-i+1; ++j)
        {
            long lef = j, rig = j+i-1;

            if (rig == lef)
            {
                dp[lef][rig] = 0;
                continue;
            }

            if (rig - lef == 1)
            {
                if (str[lef] != str[rig])
                    dp[lef][rig] = 1;
                continue;
            }

            if (str[lef] == str[rig])
            {
                dp[lef][rig] = dp[lef+1][rig-1];
                continue;
            }
            dp[lef][rig] = min(dp[lef][rig-1], dp[lef+1][rig])+1;
        }

    // Trace
    long lef = 0, rig = n-1, add = 0;
    while (lef < rig)
    {
        if (str[lef] == str[rig])
        {
            ++lef; --rig;
            continue;
        }

        if (dp[lef-add][rig] == dp[lef+1-add][rig]+1)
        {
            str.insert(str.begin()+rig+1, str[lef]);
            ++lef;
        }
        else
        {
            str.insert(str.begin()+lef, str[rig]);
            ++lef;
            ++add;
        }
    }
    return str;
}

void process()
{
    long T;
    f1 >> T;
    for (long t = 1; t <= T; ++t)
    {
        f1.ignore();
        getline(f1, str, nln);
        f2 << palindrome(str) << nln;
    }
}

void view()
{

}


int main()
{
    openf();
    data();
    process();
    view();
    closef();
    return 0;
}