| Fişierul intrare/ieşire: | superstring.in, superstring.out | Sursă | Selectie echipe ACM ICPC, UPB 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Superstring
Cel mai scurt supersir comun a 2 siruri S1 si S2 este un sir S avand numar minim de caractere si care contine atat pe S1 cat si pe S2 ca subsecvente (secvente de caractere aflate pe pozitii consecutive in S). De exemplu, cel mai scurt supersir comun al sirurilor "alba" si "bacau" este "albacau".
Fiind date doua siruri alcatuite din litere mici ale alfabetului englez, gasiti lungimea celui mai scurt supersir comun al lor.
Date de intrare
Prima linie a fisierului de intrare superstring.in contine numarul intreg T, reprezentand numarul de teste ce urmeaza. Fiecare test consta din 2 linii. Pe prima din aceste linii se afla sirul S1, iar pe a doua linie se afla sirul S2.
Date de iesire
Pentru fiecare din cele T teste, in ordinea data in fisierul de intrare, afisati in fisierul de iesire cate o linie continand lungimea celui mai scurt supersir comun.
Restrictii
- 1 ≤ T ≤ 11
- 1 ≤ lungimea oricarui sir ≤ 1 000 000
Exemplu
| superstring.in | superstring.out |
|---|---|
| 2 alba bacau resita mures | 7 8 |
