Thursday, 9 February 2017

C Program For Finding The Longest Common Subsequence of String

The study of character of strings algorithms has a vital role in algorithm design technique. Here are presenting one of the common methods which tests the matching or similarity between the two strings. The method computes the longest common subsequence from the given text.

For example:
                              Let, Sa=<KLO>
                              Let, Sb=<XKLL>
                             
                             Therefore, LCS (Sa, Sb) is <KL> 

Algorithm:



1.   Set m:=length(x)
2.   Set n:=length(y)
3.   for i=1 to m
4.         Set matrix[i,0]=0
5.   for j=0 to n
6.         Set matrix[0,j]=0
7.   for i=1 to m
8.          for j=1 to n
9.                 if(x[i]=y[j])
10.                       Set matrix[i,j]=matrix[i-1,j-1]+1
11.                       Set matrix2[i,j]="c"
12.                else if(matrix[i-1,j] > matrix[i,j-1])
13.                       Set matrix[i,j]=matrix[i-1,j]
14.                       Set matrix2[i,j]="u"
15.                else
16.                       Set matrix[i,j]=matrix[i,j-1]
17.                       Set marix2[i,j]='l'
18. return matrix and matrix2
       
PROGRAM:
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int i,j,m,n,matrix[10][10];
char x[10],y[10],matrix2[10][10];  /* x and y is the array to store both sequence */
void print(int i,int j)        
{
      if(i==0||j==0)       /* print function is used to print subsequence */
      {
            return;
      }
      if(matrix2[i][j]=='c')
      {
         
            print(i-1,j-1);         /*recursive call */
            printf("%c",y[j-1]);

      }
      else if(matrix2[i][j]=='u')   /*u stands for upper*/
      {
            print(i-1,j);
      }
      else
      {
            print(i,j-1);
      }
}
void lcs()            /*lcs function is used to generate the matrix to find lcs */
{
      m=strlen(x);
      n=strlen(y);
      for(i=0;i<=m;i++)
      {
           matrix[i][0]=0;
           matrix2[i][0]='0';
      }
      for(j=0;j<=n;j++)
      {
           matrix[0][j]=0;
           matrix2[0][j]='0';
      }
      for(i=1;i<=m;i++)
      {
           for(j=1;j<=n;j++)
           {
                if(x[i-1]==y[j-1])
                {
                      matrix[i][j]=matrix[i-1][j-1]+1;
                      matrix2[i][j]='c';
                }
                else if(matrix[i-1][j]>=matrix[i][j-1])
                {
                      matrix[i][j]=matrix[i-1][j];
                      matrix2[i][j]='u';             /*u stands for upper*/
                }
                else
                {
                      matrix[i][j]=matrix[i][j-1];
                      matrix2[i][j]='l';           /*l stands for left */
                }
           }
      }
}
int main()
{

       printf("\nEnter the first sequence: \n");
       scanf("%s",x);
       printf("\nEnter the second sequence: \n");
       scanf("%s",y);
       lcs();
       printf("\nThe longest common subsequence is: \n");
       print(m,n);
       return 0;

}

OUTPUT:

 


EmoticonEmoticon