Edit distance
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Edit distance

  1. #1
    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. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,558

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    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. #4
    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

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center