You are not logged in. Please login at www.codechef.com to post your questions!

×

Edit distance problem (dp)


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 fails.

#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;
        string *b=new string;
        getline(cin,*a);m=(*a).length()+1;//cout<<m;
        getline(cin,*b);n=(*b).length()+1;//cout<<n;
        long int **edit=new long int*[m];
        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
                {   i=(*a).begin()+x-1;j=(*b).begin()+y-1;
                    if(*i==*j){ edit[x][y]=edit[x-1][y-1];}
                    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;
}

asked 19 Jul '14, 01:30

nobeita's gravatar image

2★nobeita
15710
accept rate: 0%

edited 19 Jul '14, 12:31


include<iostream>

include <stdlib.h>

include<string.h>

using namespace std;

inline int minn(int a,int b,int c)

{ int m = a; if (m > b) m = b; if (m > c) m = c; return m; }

int main() {

char s[2001]; char s2[2001];

int** arr;

arr = new int*[ 2001 ]; 
for( size_t i = 0; i < 2001; ++i )
arr[ i ] = new int[ 2001 ];
int t;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
    int flag=0;
    scanf("%s",&s);
    scanf("%s",&s2);
    int len1=strlen(s);
    int len2=strlen(s2);
    //Aprintf("%d %d\n",len1,len2);
    //memset(arr,0,sizeof(arr));

    //for(int j=0;j<=len1;j++)
    //{
      //  for(int k=0;k<=len2;k++)
        //{
          //  arr[j][k]=0;
        //}
    //}
    for(int j=0;j<=len2;j++)
        arr[0][j]=j;
    for(int j=0;j<=len1;j++)
        arr[j][0]=j;
   /* for(int j=0;j<=len1;j++)
    {
        for(int k=0;k<=len2;k++)
        {
            printf("%d ",arr[j][k]);
        }
        printf("\n");
    }
    printf("\n\n");*/
    for(int j=1;j<=len1;j++)
    {
        for(int k=1;k<=len2;k++)
        {
            if(s[j-1]==s2[k-1])
            {
                flag=0;
            }
            else
            {
                flag=1;
            }
            //printf("%d ",flag);
            arr[j][k]=minn((arr[j][k-1]+1),(arr[j-1][k]+1),(arr[j-1][k-1]+flag));
        }
        //printf("\n");
    }

    /*for(int j=0;j<=len1;j++)
    {
        for(int k=0;k<=len2;k++)
        {
            printf("%d ",arr[j][k]);
        }
        printf("\n");
    }

*/ printf("%d\n",arr[len1][len2]); } return 0; }

link

answered 19 Jul '14, 23:08

Ankit%20Aggarwal's gravatar image

4★Ankit Aggarwal
46129
accept rate: 0%

it works and based on same dp algorithm

link

answered 19 Jul '14, 23:08

Ankit%20Aggarwal's gravatar image

4★Ankit Aggarwal
46129
accept rate: 0%

link

answered 20 Jul '14, 12:03

nobeita's gravatar image

2★nobeita
15710
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,091
×1,901
×1,115
×846

question asked: 19 Jul '14, 01:30

question was seen: 4,714 times

last updated: 20 Jul '14, 12:03