-
May 31st, 2013, 10:48 AM
#1
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
#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.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
May 31st, 2013, 01:42 PM
#3
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
#4
Re: Edit distance
got AC
Still if anyone is trying to debug.. then it should be LEFT<=TOP instead of LEFT<TOP
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|