Pagini recente » Cod sursa (job #1484808) | Istoria paginii runda/hotomana | Cod sursa (job #442274) | Cod sursa (job #1624646) | Cod sursa (job #2002599)
#include <stdio.h>
#include <stdlib.h>
#define NMax 260
int M, N, a[NMax], b[NMax];
void back(int m, int n)
{
FILE * g = fopen("cmlsc.out", "w");
int p;
int q;
int i;
int **mat;
mat = calloc(n, sizeof(int*));
for (i = 0; i < n; i++)
mat[i] = calloc(m, sizeof(int));
int j;
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++) {
if (a[j - 1] == b[i - 1])
mat[i][j] = mat[i - 1][j - 1] + 1;
else
mat[i][j] = (mat[i][j - 1] > mat[i - 1][j] ? mat[i][j - 1] : mat[i - 1][j]);
/*
for (p = 0; p < n; p++) {
for (q = 0; q < m; q++) {
fprintf(g,"%d ", mat[p][q]);
}
fprintf(g,"\n");
}*/
}
fprintf(g, "%d\n", mat[n - 1][m - 1]);
i = n - 1;
j = m - 1;
int k[NMax];
int l = 0;
while (mat[i][j] != 0) {
if (mat[i - 1][j - 1] == mat[i][j] - 1 && mat[i - 1][j] == mat[i][j-1]) {
k[l++] = a[j - 1];
i--; j--;
}
else if (mat[i][j] == mat[i - 1][j])
i--;
else
j--;
}
for (i = l-1; i > -1; i--)
(i > 0 ? fprintf(g, "%d ", k[i]) : fprintf(g, "%d", k[i]));
}
int main(void)
{
int i;
freopen("cmlsc.in", "r", stdin);
scanf("%d %d", &M, &N);
for (i = 0; i < M; i++)
scanf("%d", &a[i]);
for (i = 0; i < N; i++)
scanf("%d", &b[i]);
back(M + 1, N + 1);
return 0;
}