1.

/*
* ACM Contest training
* Problem: 10453 - Make Palindrome
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=16&problem=1394
*
* @author Christoph Goettschkes
* @version 1.0, 01/06/2011
*
* Method : Longest common Subsequence, DP
* Status : Accepted
* Runtime: 0.928
*/


import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {

public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

do {
StringBuilder out = new StringBuilder();
String input = reader.readLine();
if (input.length() == 0)
continue;

String inputReverse = new StringBuilder(input).reverse().toString();

char[] lcs = lcs(input.toCharArray(), inputReverse.toCharArray());

out.append(input.length() - lcs.length);
out.append(" ");
out.append(createNewString2(input, inputReverse, lcs));
out.append("\n");

System.out.print(out);
} while (reader.ready());
}

static String createNewString2(String in, String inRev, char[] lcs) {
int lcsLength = lcs.length;

if (lcsLength == 0 || lcsLength == in.length()) {
return in;
}

if (lcsLength == 1) {
return in + inRev.substring(1);
}

StringBuilder ret = new StringBuilder();
int leftIndex = -1, rightIndex = -1, index;

for (int i = 0; i <= lcsLength >> 1; i++) {
leftIndex = in.indexOf(lcs[i], leftIndex + 1);
}

rightIndex = leftIndex;
if ((lcsLength & 1) == 0)
rightIndex--;

for (int i = lcsLength >> 1; i > 0; i--) {
ret.insert(0, lcs[i]);
index = in.indexOf(lcs[i - 1], rightIndex + 1);
ret.insert(0, new StringBuilder(in.substring(rightIndex + 1, index)).reverse());
rightIndex = index;

index = in.lastIndexOf(lcs[i - 1], leftIndex - 1);
ret.insert(0, in.substring(index + 1, leftIndex));
leftIndex = index;
}
ret.insert(0, lcs[0]);

if (rightIndex < in.length())
ret.insert(0, new StringBuilder(in.substring(rightIndex + 1)).reverse());

if (leftIndex > 0)
ret.insert(0, in.substring(0, leftIndex));

String ret2 = new StringBuilder(ret).reverse().toString();
return ret.append(ret2.substring(((lcsLength & 1) == 0) ? 2 : 1)).toString();
}

static char[] lcs(char[] x, char[] y) {
int n = x.length;
int m = y.length;
int[][] table = new int[n + 2][m + 2];

for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++) {
if (i == 0 || j == 0) {
table[i][j] = 0;
} else if (x[i - 1] == y[j - 1]) {
table[i][j] = table[i - 1][j - 1] + 1;
} else {
table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
}
}
}
return rec(n, m, x, y, table);
}

static char[] rec(int i, int j, char[] x, char[] y, int[][] table) {
if (i == 0 || j == 0) {
return new char[0];
}

if (x[i - 1] == y[j - 1]) {
char[] ret = rec(i - 1, j - 1, x, y, table);
char[] nret = new char[ret.length + 1];
System.arraycopy(ret, 0, nret, 0, ret.length);
nret[nret.length - 1] = x[i - 1];
return nret;
}

if (table[i - 1][j] > table[i][j - 1]) {
return rec(i - 1, j, x, y, table);
}
return rec(i, j - 1, x, y, table);
}
}



2.

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Dynamic Programming
* Problem: 10453 - MakePalindrome
* Accepted: 1.212
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {

private static int[][] f;
private static String input;

private static int calc(String s)
{
f = new int[s.length()+1][s.length()+1];
for(int k = 2; k <= s.length(); k++)
for(int i = 0; i <= s.length() - k; i++)
if(s.charAt(i) == s.charAt(i+k-1))
f[k][i] = f[k-2][i+1];
else
f[k][i] = Math.min(f[k-1][i], f[k-1][i+1]) + 1;

return f[s.length()][0];
}

private static String createPalindrome(int k, int i)
{
if(k == 0)
return "";

if(k == 1)
return "" + input.charAt(i);

char first = input.charAt(i);
char last = input.charAt(i+k-1);;

if(first == last)
return first + createPalindrome(k-2,i+1) + first;

if(f[k-1][i] > f[k-1][i+1])
return first + createPalindrome(k-1,i+1) + first;
else
return last + createPalindrome(k-1,i) + last;

}

public static void main(String... args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String palindrome;
int palindromeLength;

while( (input = reader.readLine()) != null )
{
input.trim();
palindromeLength = calc(input);
palindrome = createPalindrome(input.length(), 0);

System.out.println((palindromeLength) + " " + palindrome);

}
}
}