UVA 10453 Solution - Make Palindrome

/* Solved by using Dynamic programming*/

/*
uva id: shoaib05
Accepted Time: 0.162
*/

#include<iostream>
#include<string>
#include<cstdio>

using namespace std;

string input,result;
int table[1005][1005],length,op_size;

void makePalindrome()
{
int i,j,k,left_index,right_index;
table[0][0]=0;
for(i=1;i<=length;i++)
{
table[i][i]=0;
table[i][i-1]=0;
}
for(k=1;k<=length;k++)
{
for(i=0,j=k;j<=length;i++,j++)
{
if(input[i]==input[j])
table[i][j]=table[i+1][j-1];
else
table[i][j]=(table[i+1][j]<table[i][j-1]?table[i+1][j]:table[i][j-1])+1;
}
}
op_size=table[0][length];
i=0;
j=length;
left_index=0;
right_index=length;
while(table[i][j]!=0)
{
if(input[i]==input[j])
{
i++;
j--;
left_index++;
right_index--;
}
else
{
if(table[i][j]==table[i+1][j]+1)
{
result.insert(right_index+1,1,input[i]);
i++;
left_index++;
}
else if(table[i][j]==table[i][j-1]+1)
{
result.insert(left_index,1,input[j]);
left_index++;
j--;
}

}
}
}
int main()
{
while(cin>>input)
{
length=input.size()-1;
op_size=0;
result=input;
makePalindrome();
printf("%d %s\n",op_size,result.c_str());
}
return 0;
}