Fişierul intrare/ieşire:superstring.in, superstring.outSursăSelectie echipe ACM ICPC, UPB 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.6 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/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.insuperstring.out
2
alba
bacau
resita
mures
7
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content