Form a palindrome

Solution of geeksforgeeks problem.
http://practice.geeksforgeeks.org/problems/form-a-palindrome/0

Problem:
Given a string, find the minimum number of characters to be inserted to convert it to palindrome.

For Example:
ab: Number of insertions required is 1. bab or aba
aa: Number of insertions required is 0. aa
abcd: Number of insertions required is 3. dcbabcd



Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is S.

Output:
Print the minimum number of characters.

Constraints:
1 ≤ T ≤ 50
1 ≤ S ≤ 40

Example:

Input:
3
abcd
aba
geeks

Output:
3
0
3

Solution:

Answer is ( length of the input string - length of LCS(input string, reverse of input string) )

Code:

#include<bits/stdc++.h>
using namespace std;
 
string str; // input string
string rev; // reverse of the input string
int dp[50][50]; // LCS 2-d array
 
// return length of LCS between string a and string b
int LCS(string a, string b)
{
memset(dp, 0, sizeof dp);
int a_len = a.length();
int b_len = b.length();
 
for(int i=1; i<=a_len; i++){
for(int j=1; j<=b_len; j++){
if(a[i-1]==b[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 dp[a_len][b_len];
}
 
void solve()
{
cin>>str;
rev = str;
reverse(rev.begin(), rev.end());
int lcs = LCS(str, rev);
cout<< str.length() - lcs <<endl;
}
 
int main()
{
ios_base::sync_with_stdio(0);
 
int t=1; cin>>t;
while(t--){
solve();
}
 
return 0;
}


Ideone Link:
https://ideone.com/gIRQLc