UVA 11151 - Longest Palindrome(cpp file)

Algorithm : Edit distance(DP)


#include<stdio.h>
#include<algorithm>
#include<string.h>
#define mx 1070
using namespace std;
char ch[mx],des[mx];
int arr[mx][mx],cou,len;

void init()
{
    for(int i=0; i<len; i++)
    {
        arr[i][0]=i;
    }
    for(int i=0; i<len; i++)
    {
        arr[0][i]=i;
    }
    return;
}
void edit()
{
    int i,j;
    for(i=1; i<len; i++)
    {
        for(j=1; j<len; j++)
        {
            if(ch[j]==des[i])
            {
                arr[i][j]= arr[i-1][j-1];
            }
            else
            {
              arr[i][j] = min(arr[i-1][j],arr[i][j-1]);

                arr[i][j]++;
            }
        }
    }
}
void printlav(int i, int j)
{
    if(i==0 || j==0)
    {
        return;
    }
    else if(ch[j] == des[i])
    {
        cou++;
        printlav(i-1,j-1);
    }
    else
    {
        if(arr[i-1][j]<arr[i][j-1])
        {
            printlav(i-1,j);
        }
        else
        {
             printlav(i,j-1);
        }

    }
}
int main()
{
    int i,j,test;
    scanf("%d",&test);
    getchar();
    while(test--)
    {
        gets(ch);
        if(strlen(ch)==0)
        {
            printf("0\n");
            continue;
        }
        len = strlen(ch);
        for(i=len; i>=1; i--)
        {
            ch[i]=ch[i-1];
        }
        len++;
        ch[len]='\0';
        des[0]='k';
        j=1;
        for(i=len-1; i>=1; i--)
        {
            des[j]=ch[i];
            j++;
        }
        des[len]='\0';
        cou=0;
        init();
        edit();
        printlav(len-1,len-1);

         printf("%d\n",cou);
        memset(arr,0,sizeof arr);
    }
    return 0;
}