×

# Edit distance problem (dp)

 0   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 #include #include #include 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<

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

46129
accept rate: 0%

 0 it works and based on same dp algorithm answered 19 Jul '14, 23:08 46●1●2●9 accept rate: 0%
 0 @ankit aggarwal thanks answered 20 Jul '14, 12:03 2★nobeita 1●5●7●10 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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