Cod sursa(job #1232141)

Utilizator MariaLiviaMaria Livia Chiorean MariaLivia Data 22 septembrie 2014 10:10:11
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 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()
{
    int i = m, j = n;
    while(i && 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;
}