Pagini recente » Cod sursa (job #28092) | Cod sursa (job #58353) | Cod sursa (job #1640865) | Cod sursa (job #1452936) | Cod sursa (job #272205)
Cod sursa(job #272205)
#include <stdio.h>
#define maxn 1030
int m, n, a[maxn], b[maxn], d[maxn][maxn], s[maxn];
FILE *fin = fopen("cmlsc.in", "rt"), *fout = fopen("cmlsc.out", "wt");
int main()
{
int i=0, j=0, k=0;
fscanf(fin, "%d %d", &m, &n);
for (i=1; i <= m; i++) fscanf(fin, "%d", &a[i]);
for (i=1; i <= n; i++) fscanf(fin, "%d", &b[i]);
for (i=1; i <= m; i++)
for (j=1; j <= n; j++)
if (a[i] == b[j])
d[i][j] = d[i-1][j-1] + 1;
else
if (d[i-1][j] > d[i][j-1])
d[i][j] = d[i-1][j];
else
d[i][j] = d[i][j-1];
fprintf(fout, "%d\n", d[m][n]);
i=m,j=n;
while (d[i][j] != 0)
{
if (a[i] == b[j])
{
s[++k]=b[j];
i--, j--;
}
else
if (d[i][j-1] == d[i][j])
j--;
else
i--;
}
/*for (i=1; i <= m; i++)
{
for (j=1; j <= n; j++)
fprintf(fout, "%d ", d[i][j]);
fprintf(fout, "\n");
}*/
for (i=k; i > 0; --i) fprintf(fout, "%d ", s[i]);
fclose(fin), fclose(fout);
return 0;
}