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].
