Pagini recente » Cod sursa (job #2115334) | Cod sursa (job #949748) | Cod sursa (job #996028) | Cod sursa (job #2171787) | Cod sursa (job #1168083)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdint.h>
using namespace std;
template<class S, class T>
class Solution {
public:
Solution(const char*);
void compute();
void construct(S, S);
void writeOutput(const char*);
private:
void readArray(S, vector<T>&);
void readInput();
vector<T> a, b, s;
vector<vector<T> > c;
ifstream in;
};
template<class S, class T>
Solution<S, T>::Solution(const char* fileName) {
in.open(fileName, ifstream::in);
readInput();
in.close();
}
template<class S, class T>
void Solution<S, T>::readArray(S n, vector<T>& v) {
v.resize(n);
for (S i = 0; i < n; ++i) {
in >> v[i];
}
}
template<class S, class T>
void Solution<S, T>::readInput() {
S m, n;
in >> m;
in >> n;
readArray(m, a);
readArray(n, b);
}
template<class S, class T>
void Solution<S, T>::writeOutput(const char* fileName) {
ofstream out(fileName, ofstream::out);
out << s.size() << endl;;
for (int i = 0; i < s.size(); ++i) {
out << s[i] << " ";
}
out << endl;
out.close();
}
template<class S, class T>
void Solution<S, T>::compute() {
S m = a.size(), n = b.size();
c.resize(m + 1);
for (S i = 0; i <= m; ++i) {
c[i].resize(n + 1, 0);
}
for (S i = 1; i <= m; ++i) {
for (S j = 1; j <= n; ++j) {
if (a[i - 1] == b[j - 1]) {
c[i][j] = c[i - 1][j - 1] + 1;
} else {
c[i][j] = max(c[i - 1][j], c[i][j - 1]);
}
}
}
construct(m, n);
}
template<class S, class T>
void Solution<S, T>::construct(S i, S j) {
if (i == 0 || j == 0) {
return;
}
if (a[i - 1] == b[j - 1]) {
construct(i - 1, j - 1);
s.push_back(a[i - 1]);
} else if (c[i - 1][j] > c[i][j - 1]) {
construct(i - 1, j);
} else {
construct(i, j - 1);
}
}
int main(int argc, char **argv) {
Solution<uint16_t, uint16_t> s("cmlsc.in");
s.compute();
s.writeOutput("cmlsc.out");
return 0;
}