CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Edit distance

#### Hybrid View

1. Junior Member
Join Date
May 2013
Posts
6

## 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;
}

2. ## 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.

3. Junior Member
Join Date
May 2013
Posts
6

## 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;
}```

4. Junior Member
Join Date
May 2013
Posts
6

## Re: Edit distance

got AC
Still if anyone is trying to debug.. then it should be LEFT<=TOP instead of LEFT<TOP

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)