# Edit distance

• May 31st, 2013, 10:48 AM
codedhrj
Edit distance
I tested my code for all the test cases and got correct answer but while submitting it on SPOJ, i am getting wrong answer. Can anyone help me in figuring out what's wrong with the code?

Here is the link to the original problem: http://www.spoj.com/problems/EDIST/

#include<stdio.h>
#include<string.h>
int main()
{
char a[3001],b[3001];
int t,D[2][2005],A,B,LEFT,TOP,CORNER,temp,CURR,PREV;
scanf("%d",&t);
getchar();
while(t--)
{
scanf("%s",&a);
scanf("%s",&b);

A=strlen(a);
B=strlen(b);
CURR=0;
PREV=1;
for(int i=0;i<B+1;i++)
D[CURR][i]=i;

for(int i=1;i<=A;i++)
{

CURR=(CURR+1)%2;
PREV=(PREV+1)%2;
D[CURR][0]=i;

for(int j=1;j<=B;j++)
{
LEFT=D[CURR][j-1]+1;
TOP=D[PREV][j]+1;
if(a[i-1]==b[j-1])
CORNER=D[PREV][j-1];
else
CORNER=D[PREV][j-1]+1;
if(LEFT<TOP&&LEFT<CORNER) temp=LEFT;
else if(TOP<LEFT&&TOP<CORNER) temp=TOP;
else temp=CORNER;
D[CURR][j]=temp;
}
}
printf("%d\n",D[CURR][B]);
}
return 0;
}
• May 31st, 2013, 01:00 PM
2kaud
Re: Edit distance
Please would you format your code properly with indents etc before posting. Also would you use code tags (Go Advanced, select code, click '#'). The code as posted is just about unreadable.
• May 31st, 2013, 01:42 PM
codedhrj
Re: Edit distance
Code:

```#include<stdio.h> #include<string.h> int main() {     char a[3001],b[3001];     int t,D[2][2005],A,B,LEFT,TOP,CORNER,temp,CURR,PREV;     scanf("%d",&t);     getchar();     while(t--)     {               scanf("%s",&a);               scanf("%s",&b);                             A=strlen(a);               B=strlen(b);               CURR=0;               PREV=1;               for(int i=0;i<B+1;i++)                       D[CURR][i]=i;                             for(int i=1;i<=A;i++)               {                                           CURR=(CURR+1)%2;                       PREV=(PREV+1)%2;                       D[CURR][0]=i;                                             for(int j=1;j<=B;j++)                       {                               LEFT=D[CURR][j-1]+1;                               TOP=D[PREV][j]+1;                               if(a[i-1]==b[j-1])                                               CORNER=D[PREV][j-1];                               else                                   CORNER=D[PREV][j-1]+1;                               if(LEFT<TOP&&LEFT<CORNER)          temp=LEFT;                               else if(TOP<LEFT&&TOP<CORNER)      temp=TOP;                               else                                temp=CORNER;                               D[CURR][j]=temp;                              }               }                          printf("%d\n",D[CURR][B]);        }     return 0; }```
• May 31st, 2013, 04:54 PM
codedhrj
Re: Edit distance
got AC :)
Still if anyone is trying to debug.. then it should be LEFT<=TOP instead of LEFT<TOP