Pagini recente » Cod sursa (job #1413589) | Cod sursa (job #1902607) | Cod sursa (job #1973618) | Cod sursa (job #1017405) | Cod sursa (job #1892538)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("cmlsc.in"); ofstream out("cmlsc.out");
int m, n, i, j, k, a[1026], b[1026], lcs[2052], dp[1026][1026];
int main()
{
in >> m >> n;
for (i = 1; i <= m; ++ i)
in >> a[i];
for (i = 1; i <= n; ++ i)
in >> b[i];
if (a[1] == b[1])
dp[1][1] = 1;
else
dp[1][1] = 0;
for (i = 2; i < m; ++ i)
if (b[1] == a[i])
dp[1][i] = 1;
else
dp[1][i] = dp[1][i - 1];
for (i = 2; i < n; ++ i)
if (a[1] == b[i])
dp[i][1] = 1;
else
dp[i][1] = dp[i - 1][1];
for (i = 2; i <= n; ++ i)
{
for (j = 2; j <= m; ++ j)
{
if (b[i] == a[j])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
i = n;
j = m;
while(i)
{
if (b[i] == a[j])
{
lcs[++ k] = a[j];
-- i;
-- j;
}
else
{
if (dp[i][j - 1] >= dp[i - 1][j]) -- j;
else -- i;
}
}
out << dp[n][m] << "\n";
for (i = dp[n][m]; i >= 1; -- i)
out << lcs[i] << " ";
}