Pagini recente » Cod sursa (job #3288660) | Cod sursa (job #1407090) | Istoria paginii clasament-arhiva-educationala | Cod sursa (job #2999015) | Cod sursa (job #194521)
Cod sursa(job #194521)
#include <stdio.h>
#define IN "cmlsc.in"
#define OUT "cmlsc.out"
#define MAXN 1025
int n,m,A[MAXN],B[MAXN];
int M[MAXN][MAXN];
FILE *f2;
void read()
{
FILE *f=fopen(IN,"r");
fscanf(f,"%d %d",&n,&m);
for (int i=1;i<=n;i++)
fscanf(f,"%d",&A[i]);
for (int i=1;i<=m;i++)
fscanf(f,"%d",&B[i]);
fclose(f);
}
void printare(int n,int m)
{
if (n>0 && m>0)
{
int maxi = 1;
int maxx = M[n-1][m-1];
if (M[n][m-1] > maxx)
{
maxx = M[n][m-1];
maxi = 2;
}
if (M[n-1][m] > maxx)
{
maxx = M[n-1][m];
maxi= 3;
}
switch(maxi)
{
case 2:
printare(n,m-1);
break;
case 3:
printare(n-1,m);
break;
default:
printare(n-1,m-1);
break;
}
if (A[n] == B[m] )
fprintf(f2,"%d ",A[n]);
}
}
void solve()
{
f2=fopen(OUT,"w");
int i,j;
M[0][1]=M[1][0]=M[0][0]=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
M[i][j] = M[i-1][j-1] + (A[i] == B[j]);
if (M[i][j-1] > M[i][j])
{
M[i][j] = M[i][j-1];
}
if (M[i-1][j] > M[i][j])
{
M[i][j] = M[i-1][j];
}
}
fprintf(f2,"%d\n",M[n][m]);
printare(n,m);
fprintf(f2,"\n");
fclose(f2);
}
int main()
{
read();
solve();
return 0;
}