Casanova

/* @(#)42.c
 */

#include <stdio.h>



char string1[5000],string2[5000];
char array[5000][5000];


int max(int a, int b)
{
     if (a>b)
          return a;
     return b;
}

int lcs_length (char *A, char *B)
{
     int len1,len2;
     int i,j;
     len1 = strlen (A);
     len2 = strlen (B);
     for (i=len1; i>=0;i--) {
          for (j=len2;j>=0;j--) {
               if (A[i] == '\0' || B[j] == '\0')
                    array[i][j] = 0;
               else if (A[i] == B[j])
                    array[i][j] = 1+array[i+1][j+1];
               else
                    array[i][j] = max(array[i][j+1],array[i+1][j]);
          }
     }
     return array[0][0];
}

void get_subs ()
{
     int i,j;
     int index;
     int len1,len2;
     len1 = strlen (string1);
     len2 = strlen (string2);
     i=j=index=0;
     
     while (i<len1 && j<len2) {
          if (string1[i] == string2[j]) {
               printf ("%c",string1[i]);
               i++;
               j++;
               index++;
          }
          else if (array[i+1][j]>=array[i][j+1])
               i++;
          else
               j++;
     }
}
int main()
{
     scanf ("%s\n%s",string1,string2);
     if (lcs_length(string1,string2) == 0)
          printf ("Empty");
     else 
          get_subs();

     return 0;
}