Cod sursa(job #2037166)

Utilizator sclaiciSebastian Claici sclaici Data 11 octombrie 2017 20:26:32
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <algorithm>
#include <fstream>
#include <vector>

template <class T>
std::vector<T> cmlsc(const std::vector<T> &A, const std::vector<T> &B) {
  std::vector<std::vector<int>> best(A.size() + 1, std::vector<int>(B.size() + 1));

  for (std::size_t i = 1; i <= A.size(); ++i) {
    for (std::size_t j = 1; j <= B.size(); ++j) {
      if (A[i - 1] == B[j - 1])
        best[i][j] = best[i - 1][j - 1] + 1;
      else
        best[i][j] = std::max(best[i - 1][j], best[i][j - 1]);
    }
  }

  std::vector<T> result;
  int i = A.size();
  int j = B.size();
  while (i != 0 && j != 0) {
    if (A[i - 1] == B[j - 1]) {
      result.push_back(A[i - 1]);
      i--, j--;
    } else if (best[i - 1][j] > best[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  std::reverse(result.begin(), result.end());
  return result;
}

int main() {
  std::ifstream fin("cmlsc.in");
  std::ofstream fout("cmlsc.out");

  int n, m;
  fin >> n >> m;

  std::vector<int> A(n);
  for (int i = 0; i < n; ++i)
    fin >> A[i];

  std::vector<int> B(m);
  for (int i = 0; i < m; ++i)
    fin >> B[i];

  std::vector<int> res = cmlsc<int>(A, B);
  fout << res.size() << "\n";
  for (auto x : res) {
    fout << x << " ";
  }

  return 0;
}