Se citesc doua siruri de caractere A si B. Determinati, folosind Programarea Dinamica, lungimea celui mai lung subsir comun al celor doua siruri (SCLM / LCS) - un subsir care apare, in aceeasi ordine (dar nu neaparat consecutiv), atat in A cat si in B.
- Date de intrare
- Pe prima linie se citeste sirul A. Pe a doua linie se citeste sirul B.
- Date de iesire
- Se afiseaza un singur numar: lungimea celui mai lung subsir comun.
- Restrictii
- 1 <= lungimea A, lungimea B <= 500
Exemple
Exemplul 1
Intrare
ABCBDAB BDCABA
Iesire
4
Exemplul 2
Intrare
AGGTAB GXTXAYB
Iesire
4