Cod sursa(job #1829123)

Utilizator nicuvladNicu Vlad nicuvlad Data 14 decembrie 2016 13:56:57
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#define N 1025
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

int X[N], Y[N], L[N][N];
int n,m;
void Citire()
{
  fin>>n>>m;
  for(int i=1;i<=n;++i) fin>>X[i];
  for(int i=1;i<=m;++i) fin>>Y[i];
}

void LCS()
{
  for(int i=1;i<=n;++i)
  for(int j=1;j<=m;++j)
    if(X[i]==Y[j]) L[i][j]=1+L[i-1][j-1];
    else L[i][j]=max(L[i][j-1],L[i-1][j]);
}
void Afisare()
{
  int D[N],k=0,i,j;
  fout<<L[n][m]<<'\n';
  i=n;j=m;
  while(i>0 &&j>0)
  {
    if(X[i]==Y[j])
    {
      D[++k]=X[i];i--;j--;
    }
    else if(L[i][j-1]>L[i-1][j]) j--;
          else i--;
  }
  for(i=k;i>=1;i--)fout<<D[i]<<" ";
}
int main()
{
  Citire();
  LCS();
  Afisare();

    return 0;
}