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

#include <bits/stdc++.h>

using namespace std;

ifstream cin("subsircomunmaximal.in");
ofstream cout("subsircomunmaximal.out");

int n , m , cnt;
char a[1001] , b[1001] , rez[1001];
int d[1001][1001];

int main()
{
    cin >> a >> b;
    n = strlen(a);
    m = strlen(b);

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            if(a[i - 1] == b[j - 1]) d[i][j] = d[i - 1][j - 1] + 1;
            else d[i][j] = max(d[i - 1][j] , d[i][j - 1]);

    for(int i = n ; i >= 1;)
    {
        for(int j = m ; j >= 1 ;)
            if(a[i - 1] == b[j - 1]) rez[++cnt] = a[i - 1] , i-- , j--;
            else if(d[i - 1][j] < d[i][j - 1]) j--;
            else i--;
    }

    for(int i = cnt; i >= 1 ; i--)
        cout << rez[i];
}