Edit distance problem (dp)

c-plus-plus
dynamic-programming
spoj
wrong-answer

#1

Question->http://www.spoj.com/problems/EDIST/.I used dynamic programming to solve the
standard
edit distance problem.I have checked all the corner cases.But i m
getting wrong answer on spoj.
Can anybody tell the counter case where this code fails.

#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int t;unsigned int m,n;
    string::iterator i,j;
    scanf("%d",&t);getchar();
    while(t--)//test cases
    {
        string *a=new string;
        string *b=new string;
        getline(cin,*a);m=(*a).length()+1;//cout<<m;
        getline(cin,*b);n=(*b).length()+1;//cout<<n;
        long int **edit=new long int*[m];
        for(unsigned int k=0;k<m;k++){edit[k]=new long int[n];}

        for(unsigned int x=0;x<m;x++)
        {
            for(unsigned int y=0;y<n;y++)
            {
                if(x==0&&y==0){edit[x][y]=0;}
                else if(x==0){edit[x][y]=edit[x][y-1]+1;}//insert operation
                else if(y==0){edit[x][y]=edit[x-1][y]+1;}//delete operation
                else
                {   i=(*a).begin()+x-1;j=(*b).begin()+y-1;
                    if(*i==*j){ edit[x][y]=edit[x-1][y-1];}
                    else
                    {
                        edit[x][y]=min(min(edit[x-1][y-1]+1,edit[x-1][y]+1),edit[x][y-1]+1);
                    }
                }
            }
        }

printf("%ld

",edit[m-1][n-1]);
for(unsigned int k=0;k<m;k++){delete []edit[k];}
delete edit;
delete a;
delete b;
}
return 0;
}


#2

#include
#include <stdlib.h>

#include<string.h>
using namespace std;

inline int minn(int a,int b,int c)

{
int m = a;
if (m > b) m = b;
if (m > c) m = c;
return m;
}

int main()
{

char s[2001];
char s2[2001];

int** arr;

arr = new int*[ 2001 ]; 
for( size_t i = 0; i < 2001; ++i )
arr[ i ] = new int[ 2001 ];
int t;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
    int flag=0;
    scanf("%s",&s);
    scanf("%s",&s2);
    int len1=strlen(s);
    int len2=strlen(s2);
    //Aprintf("%d %d

",len1,len2);
//memset(arr,0,sizeof(arr));

    //for(int j=0;j<=len1;j++)
    //{
      //  for(int k=0;k<=len2;k++)
        //{
          //  arr[j][k]=0;
        //}
    //}
    for(int j=0;j<=len2;j++)
        arr[0][j]=j;
    for(int j=0;j<=len1;j++)
        arr[j][0]=j;
   /* for(int j=0;j<=len1;j++)
    {
        for(int k=0;k<=len2;k++)
        {
            printf("%d ",arr[j][k]);
        }
        printf("

“);
}
printf(”

“);*/
for(int j=1;j<=len1;j++)
{
for(int k=1;k<=len2;k++)
{
if(s[j-1]==s2[k-1])
{
flag=0;
}
else
{
flag=1;
}
//printf(”%d “,flag);
arr[j][k]=minn((arr[j][k-1]+1),(arr[j-1][k]+1),(arr[j-1][k-1]+flag));
}
//printf(”
");
}

    /*for(int j=0;j<=len1;j++)
    {
        for(int k=0;k<=len2;k++)
        {
            printf("%d ",arr[j][k]);
        }
        printf("

“);
}
*/ printf(”%d
",arr[len1][len2]);
}
return 0;
}


#3

it works and based on same dp algorithm


#4

@ankit aggarwal thanks