Cod sursa(job #871464)

Utilizator ade_tomiEnache Adelina ade_tomi Data 4 februarie 2013 20:30:03
Problema Cel mai lung subsir comun Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>
int lcs[100][100],i,k,h,n,m,d[100],x[100],y[100];
int main()
{
	FILE *f,*g;
	f = fopen ( "cmlsc.in" , "r" );
	g = fopen ( "cmlsc.out" , "w" );
	fscanf( f, "%d%d" , &n ,&m );
	for( i = 1; i <= n; i++ )
		fscanf( f, "%d", &x[i] );
	for( i = 1 ;i <= m ;i++ )
		fscanf( f, "%d" , &y[i] );
	for( int k = 1; k <= n; k++ )
		for ( int h = 1; h <= m; h++ )
			if( x[k] == y[h] )
				lcs[k][h] = 1 + lcs[k-1][h-1];
			else 
				if( lcs[k - 1][h] > lcs[k][h - 1] )
					lcs[k][h] = lcs[k - 1][h];
				else 
					lcs[k][h] = lcs[k][h - 1];
	fprintf( g, "%d\n" , lcs[n][m] );
	i = 0;
	k = n;
	h = m;
	while( lcs[k][h] )
	{
		if( x[k] == y[h] )
		{
			d[ i++ ] = x[k];
			k--;
			h--;
		}
		else
			if( lcs[k][h] == lcs[k-1][h] )
				k--;
			else h--;
	}
	for( k = i - 1; k >= 0 ;k-- )
		fprintf( g, "%d ", d[k] );
	return 0;
}