Superstring

superstring

== include(page="template/taskheader" task_id="superstring") ==

Cel mai scurt supersir comun a $2$ siruri $S{~1~}$ si $S{~2~}$ este un sir $S$ avand numar minim de caractere si care contine atat pe $S{~1~}$ cat si pe $S{~2~}$ 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.

Poveste si cerinta...

h2. 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 $S{~1~}$, iar pe a doua linie se afla sirul $S{~2~}$.

...

h2. 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.

...

h2. Restrictii

* $1 ≤ T ≤ 11$
* $1 ≤ lungimea oricarui sir ≤ 1 000 000$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. superstring.in |_. superstring.out |

|2
alba
bacau
resita
mures
|7
8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="superstring") ==

2180