ID #123 · Colecția InfoAs · Operatori și expresii

Problema Cel mai lung subsir comun

Numim _cel mai lung subșir comun_ , _subșir comun maximal_ sau, în engleză, _longest common subsequence (LCS)_ a două șiruri de caractere, cel mai lung subșir, comun ambelor șiruri. Spre exemplu, pentru șirurile de caractere `in**ga** nd**ur** at` și `**g** e**a** m**ur** i`, avem subșirul comun maximal `gaur`. ## Cerință Se dau două șiruri de caractere `s` și `t`, formate doar din litere mici ale alfabetului englez. Să se determine cel mai lung subșir comun al lor. ## Date de intrare Programul citește de la tastatură, de pe prima linie, șirul `s`, iar de pe a doua linie, șirul `t`. ## Date de ieșire Programul afișează pe ecran un șir de caractere, reprezentând subșirul comun maximal pentru cele două șiruri de caractere `s` și `t`. ## Restricții și precizări * `1 ≤ lungimile șirurilor ≤ 255` * Dacă există mai multe subșiruri comune de lungime maximă, se poate afișa oricare