// Least common subsequence in O(m+n) space
// 11/5/02, BPW
// 07/17/07, slight improvement to maximizing on seam, BPW
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <sys/resource.h>

double CPUtime()
{
struct rusage rusage;
getrusage(RUSAGE_SELF,&rusage);
return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
  + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

void topSeam(char *string1,char *string2,int length1,int length2,
  int *upperSeam)
{
// Goes northwest to southeast, like conventional memory-hogging LCS
// Only needs one row + two additional elements (diagonal & saveDiagonal)
int i,j,diagonal,saveDiagonal;

for (i=0;i<length2;i++)
  upperSeam[i]=0;
if (length1/2==0)
  return;
for (j=0;
     j<length2 && string1[0]!=string2[j];
     j++)
  ;
for ( ;j<length2;j++)
  upperSeam[j]=1;
for (i=1;i<length1/2;i++)
{
  diagonal=0;
  for (j=0;j<length2;j++)
  {
    saveDiagonal=upperSeam[j];
    if (string1[i]==string2[j])
      upperSeam[j]=diagonal+1;
    else if (j>0 && upperSeam[j-1]>upperSeam[j])
      upperSeam[j]=upperSeam[j-1];
    diagonal=saveDiagonal;
  }
}
}

void bottomSeam(char *string1,char *string2,int length1,int length2,
  int *lowerSeam)
{
// Symmetric to topSeam(), but goes southeast to northwest
int i,j,diagonal,saveDiagonal;

for (i=0;i<length2;i++)
  lowerSeam[i]=0;
if ((length1+1)/2==0)
  return;
for (j=length2-1;
     j>=0 && string1[length1-1]!=string2[j];
     j--)
  ;
for ( ;j>=0;j--)
  lowerSeam[j]=1;
for (i=length1-2;i>=length1/2;i--)
{
  diagonal=0;
  for (j=length2-1;j>=0;j--)
  {
    saveDiagonal=lowerSeam[j];
    if (string1[i]==string2[j])
      lowerSeam[j]=diagonal+1;
    else if (j<length2-1 && lowerSeam[j+1]>lowerSeam[j])
      lowerSeam[j]=lowerSeam[j+1];
    diagonal=saveDiagonal;
  }
}
}

int *upperSeam,*lowerSeam;

void LCSspace(char *string1,char *string2,
              char *LCS,int length1,int length2,int *LCSlength)
{
int i,j,upperPos,lowerPos,upperMax,lowerMax,max,upperLength,lowerLength;

/**/
printf("debug - LCS of \n");
for (i=0;i<length1;i++)
  printf("%c",string1[i]);
printf("\n");
for (i=0;i<length2;i++)
  printf("%c",string2[i]);
printf("\n");
/**/

if (length1<=0 || length2<=0)
{
  (*LCSlength)=0;
  return;
}

topSeam(string1,string2,length1,length2,upperSeam);
/**/
printf("debug - upperSeam is\n");
for (i=0;i<length2;i++)
  printf("%2d %d\n",i,upperSeam[i]);
/**/
bottomSeam(string1,string2,length1,length2,lowerSeam);
/**/
printf("debug - lowerSeam is\n");
for (i=0;i<length2;i++)
  printf("%2d %d\n",i,lowerSeam[i]);
/**/

// Scan seam to get 0, 1, or 2 characters for LCS
// and determine how to divide up input strings to continue
upperPos=lowerPos=upperMax=lowerMax=max=0;
if (lowerSeam[0]>=upperSeam[length2-1])
{
  lowerPos=0;
  lowerMax=max=lowerSeam[0];
}
else
{
  upperPos=length2-1;
  upperMax=max=upperSeam[length2-1];
}

for (i=0;i<length2-1;i++)
  if (upperSeam[i]+lowerSeam[i+1]>max)
  {
    upperPos=i;
    upperMax=upperSeam[i];
    lowerPos=i+1;
    lowerMax=lowerSeam[i+1];
    max=lowerMax+upperMax;
  }
printf("debug - diagonal pair is upperSeam[%d] & lowerSeam[%d]\n",
  upperPos,lowerPos);
// The next two loops find the elements to copy into LCS
// by determining the common symbol(s)
for (upperPos=0;upperSeam[upperPos]<upperMax;upperPos++)
  ;
for (lowerPos=length2-1;lowerSeam[lowerPos]<lowerMax;lowerPos--)
  ;

(*LCSlength)=max;
if (max==0)
  return;

if (upperMax>0)
{
  // Copy into LCS
  LCS[upperMax-1]=string2[upperPos];
  for (i=length1/2-1;
       string1[i]!=string2[upperPos];
       i--)
    ;
  // Call for upper left corner subproblem
  LCSspace(string1,string2,LCS,i,upperPos,&upperLength);
  if (upperLength!=upperMax-1)
  {
    printf("Error at %d - have %d, should be %d\n",__LINE__,
      upperLength,upperMax-1);
    exit(0);
  }
}

if (lowerMax>0)
{
  // Copy into LCS
  LCS[upperMax]=string2[lowerPos];
  for (i=length1/2;
       string1[i]!=string2[lowerPos];
       i++)
    ;
  // Call for lower right corner subproblem
  LCSspace(&string1[i+1],&string2[lowerPos+1],&LCS[upperMax+1],
    length1-i-1,length2-lowerPos-1,&lowerLength);
  if (lowerLength!=lowerMax-1)
  {
    printf("Error at %d - have %d, should be %d\n",__LINE__,
      lowerLength,lowerMax-1);
    exit(0);
  }
}
}

main()
{
char string1[100],string2[100],LCS[100];
int length1,length2,LCSlength;
int i;
double startTime;

scanf("%s",string1);
scanf("%s",string2);
length1=strlen(string1);
length2=strlen(string2);
upperSeam=(int*) malloc(length2*sizeof(int));
lowerSeam=(int*) malloc(length2*sizeof(int));
if (!upperSeam || !lowerSeam)
{
  printf("Error at %d\n",__LINE__);
  exit(0);
}
startTime=CPUtime();
LCSspace(string1,string2,LCS,length1,length2,&LCSlength);
printf("LCSspace took %f CPU\n",CPUtime()-startTime);
free(upperSeam);
free(lowerSeam);
LCS[LCSlength]='\0';
printf("LCS is %s, length %d\n",LCS,LCSlength);
}