I am writing a program in c which compute the longest common subsequences between two strings. But the problem is that when the input string length is>65 it does not give the output. I am doing the the program in DEV c++. I have also tried in gcc compiler but in gcc compiler when the string length is>65 it gives some garbage value. I need to execute the program when both the input string length is >65 as I need to compare its with other algorithm. Plz help me. Its urgent. thanks in advance...
What is the size of your array for input string? 65? Show us your code (remember to use CODE tags and indentations).
Code: #include<stdio.h> #include<conio.h> #include<string.h> #include<time.h> #include<math.h> #include <stdlib.h> int sum(int,int); int main() { clock_t start, end; double cpu_time_used; char s1[1000],s2[1000],ch,ch1; int i,j,l1,l2,k,m,x[1000],p[1000],q[1000],b[1000],c[1000],y[1000],temp[1000],a=0,count=0,z=0,min,d=0,r=0,n=0,n1=0,n2=0,n3=0,count1=0,t=0; //do //{ printf("enter the 1st sequence:\n"); gets(s1); printf("enter the 2nd sequence:\n"); gets(s2); l1=strlen(s1); l2=strlen(s2); //start=clock(); //printf("length1=%d length2=%d \n",l1,l2); for(i=0;i<l1;i++) //finding matching pairs { for(j=0;j<l2;j++) { if(s1[i]==s2[j]) { k=i; m=j; p[a]=k; q[a]=m; //x[a]=sum(k,m); //printf("p[%d]=( %d,%d )\n",count,p[a],q[a]); //printf("%d %d",p[a],q[a]); a++; count++; } } } //printf("matching pairs=%d %d",p[0],q[0]); for(i=0;i<count;i++) //1st pruning operation { //i=0; for(j=0;j<r;j++) { if((p[i]==q[j])&&(q[i]==p[j])) { break; } } if(j==r) { b[r]=p[i]; c[r]=q[i]; //r++; //printf("matching pairs:p[%d]=%d%d\n",i,b[r],c[r]); r++; } } for(i=0;i<r;i++) { x[i]=sum(b[i],c[i]); //printf("matching pairs:p[%d]=(%d,%d)=%d\n",i,b[i],c[i],x[i]); } for(i=0;i<r;i++) //sorted sequence { for(j=i+1;j<r;j++) { if(x[i]>x[j]) { min=x[i]; x[i]=x[j]; x[j]=min; } } //printf("sorted sequence %d\n",x[i]); } //printf("%d",r); for(i=0;i<r;i++) { for(j=0;j<r;j++) { if((b[j]+c[j])==x[z]) { p[z]=b[j]; q[z]=c[j]; x[z]=sum(p[z],q[z]); y[z]=abs(p[z]-q[z]); //printf("sorted sequence:x[%d]=p[%d]q[%d]=(%d,%d)=%d=diff %d\n",z,z,z,p[z],q[z],x[z],y[z]); z++; } } } temp[d]=0; //temp[d-1]=0; //2nd pruning operation for(i=0;i<r;i++) { //printf("%d%d%d\n",d-1,temp[d-1],x[i]); if(temp[d-1]==x[i]) { //printf("%d%d\n",y[d-1],y[i]); if(y[d-1]>y[i]) { temp[d-1]=x[i]; p[d-1]=p[i]; q[d-1]=q[i]; y[d-1]=y[i]; //printf("temp[%d]=%d,%d\n",d-1,p[d-1],q[d-1]); } else { temp[d-1]=temp[d-1]; p[d-1]=p[d-1]; q[d-1]=q[d-1]; y[d-1]=y[d-1]; //printf("temp[%d]=%d,%d\n",d-1,p[d-1],q[d-1]); } } else { temp[d]=x[i]; p[d]=p[i]; q[d]=q[i]; y[d]=y[i]; //printf("temp[%d]=%d,%d\n",d,p[d],q[d]); d++; } } for(i=0;i<d;i++) { //printf("after 2nd pruning:temp[%d]=p[%d]q[%d]=(%d,%d)=%d\n",i,i,i,p[i],q[i],temp[i]); } //printf("%d",d); start=clock(); int comp=0; while(n<d) //algorithm begins { if((p[n2]+q[n2])==temp[n2]) { b[n]=p[n2]; c[n]=q[n2]; printf("minimum=b[%d]c[%d]=(%d,%d)\n",n,n,b[n],c[n]); } for(i=0;i<d-n3;i++) { if((p[i]>b[n])&&(q[i]>c[n])) { p[n1]=p[i]; q[n1]=q[i]; temp[n1]=sum(p[n1],q[n1]); //printf("existing matching pairs:temp[%d]=p[%d]q[%d]=(%d,%d)=%d\n",n1,n1,n1,p[n1],q[n1],temp[n1]); n1++; } } //printf("%d",n1); n3=(d-n1); n1=0; n++; comp++; } printf("no of comparision: %d\n",comp); for(i=0;i<d;i++) { if((b[i]==b[i+1])&&(c[i]==c[i+1])) { continue; } else { b[i]=b[i]; c[i]=c[i]; printf("LCS pairs:(%d,%d)\n",b[i],c[i]); count1++; } } printf("the LCS of two sequences is:"); for(i=0;i<count1;i++) { printf("%c",s1[b[i]]); } end = clock(); cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; printf("\nTime elapsed: %f\n",cpu_time_used ); //printf("\nContinue(y/n):"); getch(); //} //while(ch1=='y'||ch1=='Y'); //return 0; } int sum(int k,int m) { int s; s=k+m; return s; } this is the code for computing LCS.
Check out my function to find longest common substrings: Code: #include <stdio.h> #include <string.h> int LCS(const char *str1, const char *str2) { int len1, len2, lenS, lenL, len, iS, iL, found; const char *strS, *strL; len1 = strlen(str1); len2 = strlen(str2); if (len1 < len2) { strS = str1; lenS = len1; strL = str2; lenL = len2; } else { strS = str2; lenS = len2; strL = str1; lenL = len1; } found = 0; len = lenS; while (len > 0) { for (iL = 0; iL <= lenL - len; ++iL) { for (iS = 0; iS <= lenS - len; ++iS) { if (strncmp(strS + iS, strL + iL, len) == 0) { printf("Found longest common substring: %.*s\n", len, strS + iS); ++found; } } } if (found > 0) { return found; } --len; } puts("No common substrings found."); return 0; }
thnks for the reply. But what u written is method to compute longest common substring. In my algo its give the algo but the problem is it does not give any result for the strings of length>65.
