The longest common sub-segmentation error

Question

I need to write a program to determine the longest common subsequence.

Input:

The first argument will be a file containing two lines per line, separated by semicolons. You can assume that for each test case there is only one unique subsequence. eg.

XMJYAUZ; MZJAWXU

Output:

The longest common subsequence. Make sure that there are no blank spaces on each line that you print. eg.

meow

I use Dev C ++ .. And it compiles Fine! ... But this question is a programming challenge and when I send my answer, showing me the segmentation error!

I wrote the following code and I get a segmentation error, where am I mistaken?

#include<stdio.h> #include<stdlib.h> #include<string.h> char str1[100],str2[100]; int len1; int len2; void printLCS(char b[len1][len2],char str1[],int i,int j) { if(i==0 || j==0) return; if(b[i][j]=='c') { printLCS(b,str1,i-1,j-1); printf("%c",str1[i-1]); } else if(b[i][j]=='l') printLCS(b,str1,i,j-1); else printLCS(b,str1,i-1,j); } void Seq(char str1[],char str2[]) { int i,j; len1=strlen(str1); len2=strlen(str2); int LCS[len1+1][len2+1]; char b[len1][len2]; for(i=0;i<=len1;i++) { LCS[i][0]=0; } for(j=0;j<=len2;j++) { LCS[0][j]=0; } for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(str1[i-1]==str2[j-1]) { LCS[i][j]=1+LCS[i-1][j-1]; b[i][j]='c'; } else if(LCS[i-1][j]>=LCS[i][j-1]) { LCS[i][j]=LCS[i-1][j]; b[i][j]='u'; } else { LCS[i][j]=LCS[i][j-1]; b[i][j]='l'; } } } printLCS(b,str1,len1,len2); } int main(int argc,char *argv[]) { if(argc!=2) { printf("Invalid Number of Arguments:\n"); exit(0); } FILE *fp; fp=fopen(argv[1],"r"); if(fp==NULL) { printf("File can't be opened:\n"); exit(0); } char c; c=fgetc(fp); while(c!=EOF) { int k=0; if(c=='\n') c=fgetc(fp); while(c!=';') { str1[k]=c; k++; c=fgetc(fp); } str1[k]='\0'; c=fgetc(fp); k=0; while(c!=EOF && c!='\n') { str2[k]=c; k++; c=fgetc(fp); } str2[k]='\0'; Seq(str1,str2); printf("\n"); if(c==EOF) { break; } else c=fgetc(fp); } return 0; } 

Answer 1

I do not know the system of this site, but; I compiled without errors and the result was true.

 You didnt close file. Maybe memory leak etc. didnt allowed by site. 

And, do not use global variables unless you know another solution

This is a very bad use! ISO C90 prohibits this, anyway

 int len1; int len2; void printLCS(char b[len1][len2]... 

good luck.

Answer 2

If you have access to a Mac or Linux system, there is a fantastic tool called valgrind that can help you identify such errors: it basically runs your program on a virtual machine and controls what it reads and writes to memory.

While I cannot compile your code, I am rather suspicious of this loop:

  for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(str1[i-1]==str2[j-1]) { LCS[i][j]=1+LCS[i-1][j-1]; b[i][j]='c'; } else if(LCS[i-1][j]>=LCS[i][j-1]) { LCS[i][j]=LCS[i-1][j]; b[i][j]='u'; } else { LCS[i][j]=LCS[i][j-1]; b[i][j]='l'; } } } 

Arrays in C and C ++ start at 0, so the maximum offset you are interested in is probably strlen - 1 . Try changing the settings for loops to

 for(i=1;i<len1;i++) { for(j=1;j<len2;j++) { ... } }