Cod sursa(job #1231094)

Utilizator MariaLiviaMaria Livia Chiorean MariaLivia Data 19 septembrie 2014 15:07:53
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#define MAX 1024
using namespace std;
int m, n, a[MAX], b[MAX];
int c[MAX][MAX], solution[MAX], nr;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int maxim(int a, int b)
{
    return a > b ? a : b;
}
void Length()
{
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(a[i] == b[j])
            {
                c[i][j] = 1 + c[i-1][j-1];
            }
            else
            {
                c[i][j] = maxim(c[i-1][j], c[i][j-1]);
            }
        }
    }

}
void Decode()
{
    for(int i = m; i > 0; i--)
    {
        for(int j = n; j > 0; j--)
        {
            if(a[i] == b[j])
            {
                solution[++nr] = a[i];
                i--; j--;
            }
            else if(c[i-1][j] > c[i][j-1])
                i--;
            else
                j--;
        }
    }
}
int main()
{
    fin >> m >> n;
    for(int i = 1; i <= m; i++)
        fin >> a[i];
    for(int i = 1; i <= n; i++)
        fin >> b[i];
    Length();
    Decode();
    fout << c[m][n] << "\n";
    for(int i = nr; i > 0; i--)
        fout << solution[i] << " ";
    return 0;
}