Cod sursa(job #180331)

Utilizator mordredSimionescu Andrei mordred Data 16 aprilie 2008 21:32:29
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>
#define max(a,b) ((a>b)?a:b)

int m,n,a[100],b[100];
int suff[100][100],lcs[100][100];
int i,j,c[100],k;

int main(){
freopen("cmlsc.in","r",stdin);
freopen("cmlsc.out","w",stdout);

scanf("%d %d",&m,&n);

for(;i<m;i++)
	scanf("%d",&a[i]);
for(i=0;i<n;i++)
	scanf("%d",&b[i]);

for(i=0;i<m;i++)
	for(j=0;j<n;j++)
		{
        if(a[i]==b[j])
            suff[i][j]=1+suff[i-1][j-1];
        else
            suff[i][j]=max(suff[i][j-1],suff[i-1][j]);
        }
        
for(i=m-1,j=n-1;i>=0;)
    {
    if(a[i]==b[j])
        c[k++]=a[i],i--,j--;
    else if(suff[i-1][j]<suff[i][j-1])
        j--;
    else
        i--;
    }

printf("%d\n",k);

for(i=k-1;i>=0;i--)
    printf("%d ",c[i]);
return 0;
}