#include <stdio.h> 
#include <string.h>

#define MAX 100

int lcs_length (char x[], char y[], int n, int m) {
  int i, j, c[MAX][MAX], b[MAX][MAX]; 

  for (i=1; i<=n; i++) c[i][0]=0;
  for (j=0; j<=m; j++) c[0][j]=0;
  for (i=1; i<=n; i++) 
    for (j=1; j<=m; j++) 
      if (x[i] == y[j]) 
	c[i][j] = c[i-1][j-1] + 1;
      else if (c[i-1][j] >= c[i][j-1]) 
	c[i][j] = c[i-1][j];
      else 
	c[i][j] = c[i][j-1];
  return c[n][m];
}

int main() {
  int n, m, i, j;
  char x[MAX], y[MAX]; 
  FILE *arq;

  if ((arq = fopen("entrada.txt", "r")) == NULL) {
    printf("Problemas na leitura do arquivo de entrada.\n");
    exit(0);
  }
  fscanf(arq, "%s", x); 
  fscanf(arq, "%s", y); 
  n = strlen(x)-1;
  m = strlen(y)-1;
  for (i=n; i>0; i--) x[i] = x[i-1];
  for (j=m; j>0; j--) y[j] = y[j-1];
  printf("O comprimento de uma subseqüência máxima de %s e %s é %d.\n", x, y, lcs_length(x,y,n,m));
  return 0;
}