# PBinfo #2529 – SubsirComunMaximal – Rezolvare C++

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

## Enunț

Cerința
Se dau două șiruri de caractere, litere mici ale alfabetului englez. Să se afișeze cel mai lung subșir comun al lor.

Date de intrare
Fișierul de intrare subsircomunmaximal.in conține cele două șiruri de caractere, unul pe prima linie, unul pe cea de-a doua.

Date de ieșire
Fișierul de ieșire subsircomunmaximal.out va conține pe prima linie un șir de caractere, reprezentând cel mai lung subșir comun al celor două șiruri de caractere.

Restricții și precizări

1 ≤ lungimea unui șir ≤ 1000
dacă există mai multe subșiruri comune de lungime maximă, se poate afișa oricare dintre acestea.

Exemplu:
subsircomunmaximal.in

aaabcd
agahbdert
subsircomunmaximal.out

aabd

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define Nmax 1005
using namespace std;
ifstream fin("subsircomunmaximal.in");
ofstream fout("subsircomunmaximal.out");
char C1[Nmax], C2[Nmax];
int N, M;
int dp[Nmax][Nmax];
char ans[Nmax];
int L = 0;
int main()
{
    fin >> (C1 + 1) >> (C2 + 1);
    N = strlen(C1 + 1);
    M = strlen(C2 + 1);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(C1[i] == C2[j])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    for(int i = N, j = M; i >= 1 && j >= 1;)
    {
        if(C1[i] == C2[j])
            ans[++L] = C1[i], i--, j--;
        else
        {
            if(dp[i - 1][j] > dp[i][j - 1])
                i--;
            else
                j--;
        }
    }
    reverse(ans + 1, ans + L + 1);
    fout << (ans + 1) << "\n";
    return 0;
}
```

## Resurse

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