#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 300


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

//--------- ALOCAR O TAMANHO DOS ARQUIVOS-----------//

/*int** aloc_int_lcs(int i, int j)
  {
    int** aloc_int;
    int aux1,aux2;

    aloc_int = (int**)calloc(i,sizeof(int*));
    for(aux1 = 0; aux1 < i; aux1++)
      {
        aloc_int[aux1] = (int*)calloc(i,sizeof(int));
        for (aux2 = 0; aux2 < j; aux2++)
          {
            aloc_int[aux1][aux2] = 0;
          }
      }
    if (aloc_int == NULL)
      {
        printf("Houve um erro\n");
      }

  for (int h = 0; h<i;h++){
    for(int g = 0; g<j;g++){
    printf("%p\n",&aloc_int[h][g]);}
  }


  return aloc_int;
}*/



//--------------------  FREE ----------------------//
void free_aloc(char** aloc_char1, int tam_int1)
  {
    for(int aux3 = 0; aux3 < tam_int1; aux3++)
      {
        free(aloc_char1[aux3]);
      }
    free(aloc_char1);
  }

//-------------- ABRIR ARQUIVO -------------------//
void abrirarquivo(FILE *arq, int* tamanho, char** arquivo)
  {
    if (arq == NULL)
      {
        printf("!!!!ERROR!!!!\n");
        exit;
      }
    setbuf(stdin, NULL);
    char ln_arc[MAX];
    int aux1;
    int ln = 0;
    while (fgets(ln_arc, MAX, arq))
      {
        aux1 = strlen(ln_arc);
        arquivo[ln] = (char*)calloc(aux1+1,sizeof(char));
        strcpy(arquivo[ln], ln_arc);
        //printf("%s",arquivo[ln]);
        ln++;
      }
    *tamanho = ln;

  }


void contlinha(FILE *arquivo, int* aux1)
  {
    int ln = 0;
       if (arquivo == NULL)
      {
        printf("!!!!ERROR!!!!\n");
        exit;
      }
        char ln_arc[MAX];


        while (fgets(ln_arc, MAX, arquivo))
      {
        ln++;
      }
      *aux1 = ln;
  }



//--------------- LCS -------------------//

char** LCS(char** vetor1, char** vetor2, int p, int k,int* ind_final)
  {
    int L[p+1][k+1];
    for (int i=0; i< p+1; i++)
      {
        for (int j=0; j< k+1; j++)
          {
            if (i == 0 || j == 0)
              {
                L[i][j] = 0;
              }
            else if (strcmp(vetor1[i-1],vetor2[j-1]) == 0)
              {
                L[i][j] = L[i-1][j-1] + 1;
              }
            else
              {
                L[i][j] = max(L[i-1][j], L[i][j-1]);
              }
            }
        }
        /*for(int h = 0; h<p+1;h++){
          for(int e = 0; e<k+1;e++){
            printf(" %2d ",L[h][e]);
          }
          printf("\n");
        }*/
    int index = L[p][k];
    *ind_final = index;
    char** lcs;
    int i = p;
    int j = k;
    int aux;
    lcs = (char**)calloc(p,sizeof(char*));
    while (i > 0 && j > 0)
    {
      if (strcmp(vetor1[i-1],vetor2[j-1]) == 0)
        {
          aux = strlen(vetor1[i-1]);
          lcs[index-1] = (char*)calloc(aux+1,sizeof(char));
          strcpy(lcs[index-1],vetor1[i-1]);
          //printf("%s",lcs[index-1]);
          i--;
          j--;
          index--;
        }
      else if (L[i-1][j] > L[i][j-1])
        {
          i--;
        }
      else
        {
          j--;
        }
    }
    /*for (int i=0; i < L[p][k]; i++)
      {
        printf("%s",lcs[i]);
      }*/
  //precisa desalocar o lcs;
    return lcs;
  }



int main(int argc, char* argv[ ])
  {
    char** string1;
    char** string2;
    char** matriz_char;
    int aux1,aux2;
    int tamanho1 = 0, tamanho2 = 0, index = 0;
    int arc_1 , arc_2;

    FILE *arq1;
    FILE *arq2;
    arq1 = fopen(argv[1],"r");
    arq2 = fopen(argv[2],"r");
    //contlinha(arq1, &arc_1);
    //contlinha(arq2, &arc_2);
    //printf("%d %d\n",arc_1,arc_2);

    string1 = (char**)calloc(26,sizeof(char*));//corrigir pois esta estatico;
    abrirarquivo(arq1, &tamanho1,string1);
    string2 = (char**)calloc(34,sizeof(char*));//corrigir pois esta estatico;
    abrirarquivo(arq2, &tamanho2,string2);
    matriz_char = LCS(string1,string2,tamanho1,tamanho2,&index);
    //printf("%d\n",index);
    for (int i=0; i < index; i++)
      {
        printf("%s",matriz_char[i]);
      }
    //printf("%s",matriz_char[7]);
    fclose(arq1);
    fclose(arq2);

    free_aloc(string1,tamanho1);
    free_aloc(string2,tamanho2);

  //fprintf(stderr,"João me da dois pontos.\n");


    return 0;
  }