Edit distance standard dp problem.

[ankur12106037]

[b]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 fai

ls.[/b]

#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; //input ist string
string *b=new string; //input 2nd string
getline(cin,*a);m=(*a).length()+1;
getline(cin,*b);n=(*b).length()+1;
long int **edit=new long int*[m]; //intializing the array
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 //if x>1&&y>1
{ i=(*a).begin()+x-1;j=(*b).begin()+y-1; 
if(*i==*j){ edit[x][y]=edit[x-1][y-1];}// if same character
else
{
edit[x][y]=min(min(edit[x-1][y-1]+1,edit[x-1][y]+1),edit[x][y-1]+1);
}
}
}
}

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

[ne555]

string *a=new string; http://www.cplusplus.com/forum/general/138037/

long int **edit=new long int*[m];
delete edit; //invoking undefined behaviour 

[keskiverto]

Lack of code tags makes it hard to read.

Can you explain the idea of your DP?

[ankur12106037]

Basically we are given two strings
suppose FOOD and MONEY also mentioned in example of the question
we have to convert FOOD into MONEY and we have 3 opeartion through which we can do it.
1) Insert an element from MONEY to FOOD
2) Delete an element from FOOD
3) Replace an element from MONEY TO FOOD
but in case elements are same we will not replace it instead we will move further.

cost of each operation can be considered equal. Let it be 1:
so, Ci=Cd=Cr=1;(here i->insert,d=delete,r=replace)


let m and n be length of two strings a and b (here Food and Money resp).We take two iterators i and j
0<=i<=m & 0<=j<=n;
I used two for loops to cover each case

for insert cost(i,j)=cost(i,j-1)+Ci as insert will reduce length of string 2nd
it implies we are done with b[j]

for delete cost(i,j)=cost(i-1,j)+Cd as delete will reduce length of string ist by one it implies we are done with a[i]

for replace cost(i,j)=cost(i-1,j-1)+Cr it implies we are done with both a[i]&b[j]. but in case a[i]==b[j] we will simply do :
cost(i,j)=cost(i-1,j-1) as we are not to do any operation to make it happen.


after covering all the cases we will choose the path which cost the minimum

i consider the 2d matrix for this and cost(m)(n) give me the leat cost

[keskiverto]

There are subtle differences between your implementation and this: http://en.wikipedia.org/wiki/Levenshtein_distance

[ankur12106037]

thanks @ keskiverto i got the mistake in my logic.