Cod sursa(job #195151)

Utilizator iondionGeorge Pascu iondion Data 16 iunie 2008 21:10:47
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.88 kb
/**
   LUNGIME-CMLSC( X, Y )
   1. m<-lungime[X]
   2. n<-lungime[Y]
   3. pentru i<-1, m executa
   4.        c[i,0]<-0
   5. pentru j<-0, n executa
   6.        c[0, j]<-0
   7. pentru i<-1, m executa
   8.        pentru j<-1, n executa
   9.               daca xi=yj
   10.                   c[i,j]=c[i-1][j-1]+1
   11.              altfel
   12.                    daca c[i-1, j]>=c[i, j-1]
   13.                         c[i,j]<-c[i-1, j]
   14.                    altfel
   15.                         c[i, j]<-c[i, j-1]
   16. returneaza c
   
   SCRIE-CMLSC( X, i, j )
   1. daca i=0 sau j=0 atunci
   2.      revenire
   3. daca c[i-1, j-1] = c[i, j]+1 atunci
   4.      SCRIE-CMLSC( X, i-1, j-1 )
   5.      tipareste xi
   6. altfel daca c[i, j] = c[i-1, j]
   7.      SCRIE-CMLSC( X, i-1, j )
   8. altfel
   9.      SCRIE-CMLSC( X, i, j-1 )
**/
#include <fstream>
#include <string>
#define NMax 100
using namespace std;
int c[NMax][NMax];
//int c1[NMax], c2[NMax];
int X[NMax], Y[NMax];
int m, n;

ofstream fout("cmlsc.out");

void lungime( int *X, int *Y )
{
     unsigned i, j;
     for( i=1; i<=m; i++ )
          c[i][0] = 0;
     for( j=0; j<=n; j++ )
          c[0][j] = 0;
     for( i=1; i<=m; i++ )
          for( j=1; j<=n; j++ )
               if( X[i]==Y[j] )
                   c[i][j] = c[i-1][j-1] + 1;
               else
                   if( c[i-1][j] >= c[i][j-1] )
                       c[i][j] = c[i-1][j];
                   else
                       c[i][j] = c[i][j-1];
}
/*
  Functia urmatoare e geniala pt. ca foloseste doar 2 vectori de lungime n, pt. a face treaba matricii c[n][n]
  in a calcula lungimea CMLSC

int lung( char *X, char *Y )
{
    unsigned m = strlen( X );
    unsigned n = strlen( Y );
    unsigned i, j;
    c1[0]=c2[0]=0;
    for( i=1; i<=m; i++ )
    {
         for( j=1; j<=n; j++ )
         {
              if( X[i] == Y[j] )
                  c2[j] = c1[j-1]+1;
              else if( c1[j] >= c2[j-1] )
                   c2[j] = c1[j];
              else
                   c2[j] = c1[j-1];
         }
         for( j=1; j<=n; j++ )
              c1[j] = c2[j];
    }
    return c1[n];
}
*/
void printCMLSC( int *X, int i, int j )
{
     if( i==0 || j==0 )
         return;
     if( c[i-1][j-1] = c[i][j]+1 )
     {
         printCMLSC( X, i-1, j-1 );
         fout << X[i] << ' ';
     }
     else if ( c[i-1][j] == c[i][j] )
          printCMLSC( X, i-1, j );
     else
          printCMLSC( X, i, j-1 );
}

void citire( int *X, int *Y )
{
     ifstream fin( "cmlsc.in" );
     int i;
     fin >> m;   fin >> n;
     for( i=0; i<m; i++ )
          fin >> X[i];
     for( i=0; i<n; i++ )
          fin >> Y[i];
     fin.close();
}

int main()
{
    citire( X, Y );
    lungime( X, Y );
    fout << c[m][n] << '\n';
    printCMLSC( X, m, n );
    return 0;
}