Pagini recente » Cod sursa (job #1425005) | Cod sursa (job #1139590) | Cod sursa (job #1383267) | Cod sursa (job #1112790) | Cod sursa (job #769861)
Cod sursa(job #769861)
#include <iostream>
#include <fstream>
#include <cstring>
#include <stdlib.h>
using namespace std;
int* a;
int* b;
int** s;
int m, n;
int max (int a, int b)
{
if (a > b)
return a;
return b;
}
struct aaa
{
int cat;
char* care;
};
/*
char* determinasubsir(int i, int j)
{
if (i && j)
{
if (a[i - 1] == b[j - 1])
{
char* c;
c = new char[10];
c = itoa(a[i - 1], c, 10);
return (strcat(strcat(determinasubsir(i - 1, j - 1), " "), c));
}
else if (s[i][j] == s[i - 1][j])
return determinasubsir(i - 1, j);
else
return determinasubsir(i, j - 1);
}
return "";
}*/
aaa cmlsc()
{
s = new int*[m + 2];
for (int i = 0; i <= m; i++)
{
s[i] = new int[n + 2];
s[i][0] = 0;
}
for (int j = 0; j <= n; j++)
s[0][j] = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (a[i] == b[j])
s[i + 1][j + 1] = s[i][j] + 1;
else
s[i + 1][j + 1] = max(s[i + 1][j], s[i][j + 1]);
}
}
aaa f;
f.cat = s[m][n];
f.care = new char[f.cat];
//f.care = determinasubsir(m, n);
char* p;
int k = s[m][n];
p = new char[k];
int i = m, j = n;
while (i && j )
{
if (a[i - 1] == b[j - 1])
p[--k] = a[i - 1] + '0', i--, j--;
else if (s[i][j] == s[i - 1][j])
i--;
else
j--;
}
strcpy(f.care, p);
return f;
}
int main()
{
ifstream in ("cmlsc.in");
ofstream out ("cmlsc.out");
in >> m >> n;
a = new int[m];
b = new int[n];
for (int i = 0; i < m; i++)
in >> a[i];
for (int i = 0; i < n; i++)
in >> b[i];
aaa f = cmlsc();
out << f.cat << "\n";
for (int i = 0; i < f.cat; i++)
out << f.care[i] << " ";
return 0;
}