Cod sursa(job #834501)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 14 decembrie 2012 15:41:27
Problema Cel mai lung subsir comun Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>

int main(){
    std::ifstream fin("cmlsc.in");
    std::ofstream fout("cmlsc.out");
    unsigned short n,m;
    fin>>m>>n;
    std::vector<unsigned short> a(n), b(n);
    for(unsigned short i=0;i<m;++i) fin>>a[i];
    for(unsigned short i=0;i<n;++i) fin>>b[i];

    std::vector< std::vector<unsigned short> > lcs(m,std::vector<unsigned short>(n));
    for(unsigned short i=0;i<m;++i) lcs[i][0]=(b[0]==a[i]);
    for(unsigned short i=0;i<n;++i) lcs[0][i]=(a[0]==b[i]);
    for(unsigned short i=1;i<m;++i)
        for(unsigned short j=1;j<n;++j)
            if(a[i]==b[j]) lcs[i][j]=lcs[i-1][j-1]+1;
            else lcs[i][j]=(lcs[i-1][j]>lcs[i][j-1]?lcs[i-1][j]:lcs[i][j-1]);
    std::vector<unsigned short> rseq(lcs[m-1][n-1]);
    int pos=0; unsigned short i=m-1,j=n-1;
    while(pos<lcs[m-1][n-1]){
        if(a[i]==b[j]){ rseq[pos++]=a[i]; --i; --j; }
        else if(lcs[i][j-1]>lcs[i-1][j]) --j;
        else --i;
    }
    fout<<lcs[m-1][n-1]<<'\n';
    for(pos--;pos>=0;--pos) fout<<rseq[pos]<<' ';
    fout<<'\n';
}