Don't allocate too much static memory in stack, it will cause
troubles. You are doing int[2000][2000], i.e. 2000*2000*4 bytes of
memory in stack. Use dynamic memory allocation for such large chunk. I
modified your code as below and it doesn't give seg fault.
#include<stdio.h>
#include <malloc.h>
#include<string.h>
#define MAX 2000
using namespace std;
int minimum(int a,int b,int c)
{
if(a<b && a<c) return a;
if(b<c) return b;
return c;
}
int LevenshteinDistance(char *a, char *b)
{
int **d;
int m=0,n=0,i,j;
char s[MAX]="0";
char t[MAX]="0";
d = (int **)malloc(MAX*sizeof(int));
for (i=0;i<MAX;i++)
d[i] = (int *)malloc(MAX*sizeof(int));
strcat(s,a);
strcat(t,b);
m=strlen(s);
n=strlen(t);
printf("%s%s",s,t);
for(i=0;i<=m;i++) d[i][0]=i ;
for(j=0;j<=n;j++) d[0][j]=j;
for(j=1;j<=n;j++)
{
for(i=1;i<=m;i++)
{
if (s[i] == t[j])
d[i][j]=d[i-1][j-1];
else
d[i][j]=minimum(d[i-1][j] +
(s[i]==t[i]?0:1),d[i][j-1] +
1,d[i-1][j-1] + 1 );
}
}
//TODO: Free "d"
return d[m][n];
}
int main()
{
int t,ed;
char s1[MAX],t1[MAX];
scanf("%d",&t);
while( t--)
{
scanf("%s%s",s1,t1);
//cout<<s1<<t1<<endl;
ed=LevenshteinDistance(s1,t1);
printf("%d\n",ed);
}
return 0;
}
On Sun, Jul 3, 2011 at 9:08 PM, HARSH PAHUJA <[email protected]> wrote:
>
>
> ---------- Forwarded message ----------
> From: HARSH PAHUJA <[email protected]>
> Date: Sun, Jul 3, 2011 at 8:37 AM
> Subject: anu_test Segmentation fault
> To: [email protected]
>
>
> http://www.ideone.com/QuMcn
> plzz help.........
> y the above program is giving seg fault
>
> #include<stdio.h>
> #include<string.h>
> #define MAX 2000
> //using namespace std;
> int minimum(int a,int b,int c)
> {
> if(a<b && a<c) return a;
> if(b<c) return b;
> return c;
> }
> int LevenshteinDistance(char a[], char b[])
> {
> int d[2000][2000]={0};
> int m=0,n=0,i,j;
> char s[MAX]="0";
> char t[MAX]="0";
> strcat(s,a);
> strcat(t,b);
> m=strlen(s);
> n=strlen(t);
> printf("%s%s",s,t);
> for(i=0;i<=m;i++) d[i][0]=i ;
> for(j=0;j<=n;j++) d[0][j]=j;
> for(j=1;j<=n;j++)
> {
> for(i=1;i<=m;i++)
> {
> if (s[i] == t[j])
> d[i][j]=d[i-1][j-1];
> else
> d[i][j]=minimum(d[i-1][j] + (s[i]==t[i]?0:1),d[i][j-1] + 1,d[i-1][j-1] + 1
> );
> }
> }
> return d[m][n];
> }
>
> int main()
> {
> int t,ed;
> char s1[MAX],t1[MAX];
> scanf("%d",&t);
> while( t--)
> {
> scanf("%s%s",s1,t1);
> //cout<<s1<<t1<<endl;
> ed=LevenshteinDistance(s1,t1);
> printf("%d\n",ed);
> }
> return 0;
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "anu testing" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/anutesting?hl=en.
>
>
>
> --
> HARSHIT PAHUJA
> M.N.N.I.T.
> ALLAHABAD
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
