# PBinfo #2139 – codul – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Principala misiune a unei expediții științifice este de a studia evoluția vieții pe o planetă nou descoperită. În urma studiilor efectuate, cercetătorii au asociat fiecărui organism viu descoperit pe acea planetă un cod caracteristic. Codul caracteristic este un număr natural de maximum 200 de cifre zecimale nenule. De asemenea, cercetătorii au observat că pentru orice organism viu de pe planetă, codurile caracteristice ale strămoșilor săi pe scara evoluției se pot obține prin ștergerea unor cifre din codul caracteristic al organismului respectiv, iar un organism este cu atât mai evoluat cu cât codul său caracteristic are o valoare mai mare.

Cerința
Date fiind codurile caracteristice ale două organisme vii diferite, scrieți un program care să determine codul caracteristic al celui mai evoluat strămoș comun al lor.

Date de intrare
Fișierul de intrare codul.in conține pe prima linie a, codul caracteristic al primului organism, iar pe linia a doua b, codul caracteristic al celui de-al doilea organism.

Date de ieșire
Fișierul de ieșire codul.out conține pe prima linie p, codul celui mai evoluat strămoș comun al lui a şi b.

Restricții și precizări

lungimile celor două șiruri sunt numere naturale mai mici sau egale cu  200

Exemplu:
codul.in

7145
847835
codul.out

75

## Cod sursă C++

```cpp
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("codul.in");
ofstream fout("codul.out");
int dp[205][205], n, m;
char a[205], b[205];
void LCS()
{
    int i, j;
    for(i = n - 1; i >= 0; i--)
        for(j = m - 1; j >= 0; j--)
        {
            if(a[i] == b[j]) dp[i][j] = 1 + dp[i + 1][j + 1];
            else dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
        }
}
void Search(int i1, int j1, int k)
{
    int i, j, p1 = 0, p2 = 0;
    char mx = '0';
    if(k >= 1)
    {
        for(i = i1; i < n; i++)
        {
            for(j = j1; j < m; j++)
                if(dp[i][j] == k && a[i] == b[j] && a[i] > mx)
                {
                    mx = a[i];
                    p1 = i;
                    p2 = j;
                }
        }
        fout << mx;
        Search(p1 + 1, p2 + 1, k - 1);
    }
}
int main()
{
    fin >> a >> b;
    n = strlen(a);
    m = strlen(b);
    LCS();
    Search(0,0,dp[0][0]);
    fout << "\n";
    fout.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2139)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2139/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2139/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)