fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #define MAX 100
  4. char X[MAX],Y[MAX];
  5. int i,j,m,n,c[MAX][MAX],b[MAX][MAX];
  6.  
  7. // function to find the length of LCS
  8.  
  9. int LCSlength() 
  10.  
  11. {
  12.            m=strlen(X);
  13.            n=strlen(Y);
  14.            for (i=1;i<=m;i++) c[i][0]=0;
  15.            for (j=0;j<=n;j++) c[0][j]=0;
  16.            for (i=1;i<=m;i++)
  17.            for (j=1;j<=n;j++) {
  18.                          if (X[i-1]==Y[j-1]) {
  19.                                   c[i][j]=c[i-1][j-1]+1;
  20.                                   b[i][j]=1; /* from north west */
  21.                          }
  22.                         else if (c[i-1][j]>=c[i][j-1]) {
  23.                                   c[i][j]=c[i-1][j];
  24.                                   b[i][j]=2; /* from north */
  25.                        }
  26.                        else {
  27.                                   c[i][j]=c[i][j-1];
  28.                                   b[i][j]=3; /* from west */
  29.                        }
  30.           }
  31.           return c[m][n];
  32. }
  33.  
  34. void printLCS(int i,int j) 
  35.  
  36. {
  37.                   if (i==0 || j==0) return;
  38.                   if (b[i][j]==1) {
  39.                          printLCS(i-1,j-1);
  40.                          printf("%c",X[i-1]);
  41.  
  42.                  }
  43.                  else if (b[i][j]==2)
  44.                          printLCS(i-1,j);
  45.                  else
  46.                          printLCS(i,j-1);
  47. }
  48.  
  49.  
  50. int main()
  51.  
  52.  {
  53.                 while (1) {
  54.                             gets(X);
  55.                             if (feof(stdin)) break; /* press ctrl+z to terminate */
  56.                             gets(Y);
  57.                             printf("LCS length -> %d\n",LCSlength()); /* count length */
  58.                             printLCS(m,n); /* reconstruct LCS */
  59.                             printf("\n");
  60.                }
  61. }
Success #stdin #stdout 0.01s 2804KB
comments (?)
stdin
copy 
ABCBDAB
BDCABA
stdout
copy 
LCS length -> 4
BCBA
https://ideone.com/4Mtc2
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!