Cod sursa(job #1599099)

Utilizator andreib888Balan Andrei andreib888 Data 13 februarie 2016 16:42:08
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <iostream>
using namespace std;
//#define FOR(a) for(int i=1;i<=n;i++)

ifstream f("cmlsc.in");
ofstream g("cmlsc.out");

int m, n, A[1500], B[1500], T[1500], L[1500];

void citire()
{
    int i;
    f>>m>>n;
    for(i=1;i<=m;i++) f>>A[i];
    for(i=1;i<=n;i++) f>>B[i];
}

void cmm(int k, int &l, int &t)
{
    for(int i=k+1;i<=m;i++)
        if(L[i]>l)
        {
            l=L[i];
            t=i;
        }
}

int main()
{
    int i, j, l, t;
    citire();
    for(i=m;i>=1;i--)
        for(j=n;j>=1;j--)
            if(A[i]==B[j])
            {
                //cout<<"A "<<A[i]<<" B "<<B[j]<<"\n";
                l=t=0;
                cmm(i,l,t);
                L[j]=l+1;
                T[j]=t;
                //FOR(m) cout<<T[i]<<" "; cout<<"\n";
                //FOR(m) cout<<L[i]<<" "; cout<<"\n\n";
            }
    int maxim=0;
    for(i=1;i<=m;i++)
        if(L[i]>maxim)
        {
            maxim=L[i];
            j=i;
        }
    g<<maxim<<"\n";
    for(i=1;i<=maxim;i++)
    {
        g<<A[j]<<" ";
        j=T[j];
    }
    //for(i=1;i<=m;i++) cout<<T[i]<<" "; cout<<"\n";
    //for(i=1;i<=m;i++) cout<<L[i]<<" "; cout<<"\n";
    return 0;
}