Question

#2528 LungimeSubsirComunMaximal
Cerința
Se dau două șiruri de caractere, litere mici ale alfabetului englez. Să se determine lungimea celui mai lung subșir comun al lor.

Answer 1

Răspuns:

# include < fstream >

# include < cstring >

# define dim 1005

using namespace std;

ifstream fin("lungimesubsircomunmaximal.in");

ofstream fout("lungimesubsircomunmaximal.out");

short int A[dim][dim];

///sirul x pe coloana

///sirul z pe linie

char x[dim],y[dim];

int main()

{

   fin >> x >> y;

   int N=strlen(x);

   int M=strlen(y);

   for(int i=1; i<=N; i++)

       for(int j=1; j<=M; j++)

       {

           if(x[i-1]==y[j-1])

               A[i][j]=A[i-1][j-1]+1;

           else if(A[i-1][j]>=A[i][j-1])

               A[i][j]=A[i-1][j];

           else

               A[i][j]=A[i][j-1];

       }

   fout << A[N][M];

   return 0;

}

Explicație:

Structura de optim a unui SCM

Dacă avem două șiruri de elemente X={x1,x2,x3,...,xm}, cu m elemente și

Y={y1,y2,y3,...,yn}

cu n elemente atunci Z={z1,z2,z3,...,zk}este un SCM cu K elemente. El se construiește astfel:

1. Daca Xm=Yn atunci am găsit un element comun celor două șiruri (Xm=Yn=Zk) și rezultă că mai

• trebuie să căutăm SCM al șirurilor Xm-1 și Yn-1, deci avem lungimea SCM(Xm-1, Yn-1)+1

2. Dacă xm≠yn atunci determina lungimea SCM(Xm,Yn-1) și lungimea SCM(Xm-1, Yn)

vom alege valoarea maximă dintre ele.

Vom utiliza un tablou bidimensional C cu m+1 linii( de la 0 la m) si n+1 coloane(de la 0 la n) al cărui

elemente le vom calcula în ordinea crescătoare a liniilor( de sus în jos pe liniiși de la stânga la dreapta pe coloane).

Inițial vom completa linia 0 și coloana 0 cu valoarea 0. Lungimea maximă a SCM(Xm, Yn) se va găsi în C[m][n].