Cod sursa(job #1460731)

Utilizator borcanirobertBorcani Robert borcanirobert Data 13 iulie 2015 18:12:38
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
/** Care este cel mai lung subsir comun dintre sirurile a si b?
Solutia: Programare dinamica pe o matrice D;
Complexitate: O(N*M);
In sirul s se alfa raspunsul.
**/
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

const int MAX = 1024;
vector<int> a;
vector<int> b;
vector<int> s;
int N, M;
int D[MAX][MAX];
int x;
int ns;

int main()
{
    int i, j;

    fin >> N >> M;
    a.push_back(0);
    b.push_back(0);
    s.push_back(0);
    for ( i = 1; i <= N; i++ )
    {
        fin >> x;
        a.push_back(x);
    }
    for ( i = 1; i <= M; i++ )
    {
        fin >> x;
        b.push_back(x);
    }

    a.resize(N + 1);
    b.resize(M + 1);

    for ( i = 1; i <= N; i++ )
        for ( j = 1; j <= M; j++ )
            if ( a[i] == b[j] )
                D[i][j] = D[i - 1][j - 1] + 1;
            else
                D[i][j] = max( D[i - 1][j], D[i][j - 1] );

    for ( i = N, j = M; i && j; )
        if ( a[i] == b[j] )
        {
            s.push_back(a[i]), i--, j--;
            ns++;
        }
        else
            if ( D[i - 1][j] > D[i][j - 1] )
                i--;
            else
                j--;

    s.resize(ns + 1);

    fout << D[N][M] << '\n';
    for ( i = ns; i > 0; i-- )
        fout << s[i] << ' ';

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