Cod sursa(job #1933634)

Utilizator bflorin97Bardas Florin bflorin97 Data 20 martie 2017 20:45:04
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

ifstream fin;
ofstream fout;

string x = "";
string y = "";

string LCS (string x, string y) {
    if (x.length() == 0 || y.length() == 0)
        return "";
    if (x[x.length() - 1] == y[y.length() - 1])
        return LCS (*(new string(x, 0, x.length() - 1)), *(new string(y, 0, y.length() - 1))) + x[x.length() - 1];

    string a = LCS (*(new string(x, 0, x.length() - 1)), y);
    string b = LCS (x, *(new string(y, 0, y.length() - 1)));
    return a.length() > b.length() ? a : b;
}

int main (int argc, char** argv) {

    fin.open ("cmlsc.in", ifstream::in);
    fout.open ("cmlsc.out", ofstream::out);

    int n, m;
    int t;
    string res;

    fin >> n >> m;
    for (int i = 0; i < n; i ++) {
        fin >> t;
        x += (char) t;
    }
    for (int i = 0; i < m; i ++) {
        fin >> t;
        y += (char) t;
    }
    // cout << x << " " << y << endl;

    res =  LCS (x, y);
    fout << res.length() << endl;
    for (int i = 0; i < res.length(); i++)
        fout << (int)res[i] << " ";

    fin.close();
    fout.close();
}