Cod sursa(job #243211)

Utilizator StigmaSimina Pitur Stigma Data 12 ianuarie 2009 14:05:37
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream.h>
#include <fstream.h>

ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

int a[1024],k, n,m, b[1024], c[1024][1024], v[1024];



int main()
{int i,j;
fin>>n>>m;
for (i=1;i<=n;i++) fin>>a[i];
for (i=1;i<=m;i++) fin>>b[i];

for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
  if (a[i]==b[j])
   c[i][j]=c[i-1][j-1]+1;
   else
    {c[i][j]=c[i-1][j];
     if (c[i][j]<c[i][j-1])
	c[i][j]=c[i][j-1];
    }

fout<<c[n][m]<<endl;

i=n;j=m;
k=c[n][m];

while (i>0 && j>0)
 if(a[i]==b[j])
   {v[k]=a[i];
    k--;
    i--; j--;
    }
   else
    if(c[i][j]==c[i][j-1]) j--;
      else i--;


for (i=1;i<=c[n][m];i++)
fout<<v[i]<<" ";

fout.close();
return 0;
}