1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

help to compute longest common subsequence between two strings

Discussion in 'C' started by arindam.kotal, Apr 21, 2013.

  1. arindam.kotal

    arindam.kotal New Member

    Joined:
    Nov 4, 2012
    Messages:
    13
    Likes Received:
    0
    Trophy Points:
    0
    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...
     
  2. DRK

    DRK New Member

    Joined:
    Apr 13, 2012
    Messages:
    44
    Likes Received:
    3
    Trophy Points:
    0
    What is the size of your array for input string? 65? :)

    Show us your code (remember to use CODE tags and indentations).
     
  3. arindam.kotal

    arindam.kotal New Member

    Joined:
    Nov 4, 2012
    Messages:
    13
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  4. DRK

    DRK New Member

    Joined:
    Apr 13, 2012
    Messages:
    44
    Likes Received:
    3
    Trophy Points:
    0
    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;
    }
     
  5. arindam.kotal

    arindam.kotal New Member

    Joined:
    Nov 4, 2012
    Messages:
    13
    Likes Received:
    0
    Trophy Points:
    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.
     

Share This Page