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

#define MAX 100

int lcs_length_rec (char x[], char y[], int n, int m) {
  int aux1, aux2; 

  if (n == 0 || m == 0) 
    return 0;
  else if (x[n] == y[m]) 
    return lcs_length_rec(x, y, n-1, m-1) + 1;
  else {
    aux1 = lcs_length_rec(x, y, n, m-1);
    aux2 = lcs_length_rec(x, y, n-1, m);
    if (aux1 >= aux2) 
      return aux1;
    else 
      return aux2;
  }
}

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_rec(x,y,n,m));
  return 0;
}