Cod sursa(job #1892538)

Utilizator alxi.2001Alex Ionescu alxi.2001 Data 25 februarie 2017 02:02:30
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#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] << " ";
}