DaniWeb IT Discussion Community

Code Snippets (http://www.daniweb.com/code/)
-   c (http://www.daniweb.com/code/c.html)
-   -   Longest Common Subsequence (http://www.daniweb.com/code/snippet767.html)

chandrabhanu c syntax
Oct 5th, 2007
This program in C finds 2 Longest common subsequence of 2 given strings(say X and Y),entered without any space on the screen individually,altering X and Y strings.I compiled and executed this above program successfully in Dev Cpp compiler as a C file(not a c++ file).
 

  1. #include<stdio.h>
  2. #include<conio.h>
  3. #include<string.h>
  4. void print_lcs(char b[][20],char x[],int i,int j)
  5. {
  6.      if(i==0 || j==0)
  7.       return;
  8.      if(b[i][j]=='c')
  9.       {
  10.        print_lcs(b,x,i-1,j-1);
  11.        printf(" %c",x[i-1]);
  12.        }
  13.       else if(b[i][j]=='u')
  14.        print_lcs(b,x,i-1,j);
  15.       else
  16.        print_lcs(b,x,i,j-1);
  17. }  
  18. void lcs_length(char x[],char y[])
  19. {
  20.      int m,n,i,j,c[20][20];
  21.      char b[20][20];
  22.      m=strlen(x);
  23.      n=strlen(y);    
  24.      for(i=0;i<=m;i++)
  25.       c[i][0]=0;
  26.      for(i=0;i<=n;i++)
  27.       c[0][i]=0;
  28.      for(i=1;i<=m;i++)
  29.       for(j=1;j<=n;j++)
  30.       {
  31. 	if(x[i-1]==y[j-1])
  32. 	 {
  33. 	   c[i][j]=c[i-1][j-1]+1; 
  34. 	   b[i][j]='c';           \\c stands for left upright cross
  35. 	   }
  36. 	 else if(c[i-1][j]>=c[i][j-1])
  37. 	 {
  38. 	      c[i][j]=c[i-1][j];
  39. 	      b[i][j]='u';         \\u stands for upright or above
  40. 	      }
  41. 	 else
  42. 	 {
  43. 	     c[i][j]=c[i][j-1];
  44. 	     b[i][j]='l';         \\l stands for left
  45. 	     }
  46. 	}          
  47.     print_lcs(b,x,m,n);      
  48.  }     
  49. void lcs()
  50. {
  51.      int i,j;
  52.      char x[20],y[20];     
  53.      printf("1st sequence:");
  54.      gets(x);
  55.      printf("2nd sequence:");
  56.      gets(y); 
  57.      printf("\nlcs are:");
  58.      lcs_length(x,y); 
  59.      printf("\n");
  60.      lcs_length(y,x);   
  61.  }
  62. main()
  63. {
  64.      char ch;
  65.      do
  66.      {
  67.            lcs();
  68.            printf("\nContinue(y/n):");
  69.            ch=getch();
  70.            }
  71.      while(ch=='y'||ch=='Y');
  72. }