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.

Date de intrare

Fișierul de intrare lungimesubsircomunmaximal.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 lungimesubsircomunmaximal.out va conține pe prima linie numărul L, reprezentând lungimea subșirului comun maximal al celor două cuvinte.

Restricții și precizări

• 1 ≤ lungimea unui șir ≤ 1000

Exemplu

lungimesubsircomunmaximal.in

aaabcd
agahbdert

lungimesubsircomunmaximal.out

4

#include <bits/stdc++.h>

using namespace std;

ifstream cin("lungimesubsircomunmaximal.in");
ofstream cout("lungimesubsircomunmaximal.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]);

    cout << d[n][m];
}