SPOJ AIBOHP - Aibohphobia

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[6109][6109];
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        string s1,s2;
        cin>>s1;
        s2=s1;
        reverse(s2.begin(),s2.end());
        memset(dp,0,sizeof(dp));
        for(i=s1.size()-1;i>=0;i--)
        {
            for(j=s2.size()-1;j>=0;j--)
            {
                if(s1[i]==s2[j])
                {
                    dp[i][j]=1+dp[i+1][j+1];
                }
                else
                {
                    dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        cout<<s1.size()-dp[0][0]<<endl;
    }
    return 0;
}