ratina

Ratina

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

Poveste si cerinta...

Limba ratina are doar $N$ cuvinte, numerotate de la $1$ la $N$. Doua sau mai multe cuvinte se numesc $k-asemenea$ daca au primele $k$ litere identice. Gradul de asemanare intre $t$ cuvinte este $k$ daca cele $t$ cuvinte sunt $k-asemenea$, dar nu sunt $(k+1)-asemenea$.
 
h2. Cerinta
 
Scrieti un program care pentru un set de $t$ cuvinte dat, raspunde la interogari de genul: "Care este gradul de asemanare intre cuvintele $x{~1~} x{~2~} ... x{~t~}$" ?

h2. Date de intrare

...

Fisierul de intrare $ratina.in$ va contine pe prima linie doua numere naturale $N M$, separate printr-un spatiu, reprezentand numarul de cuvinte din limba ratina, respectiv numarul de interogari.
Urmatoarele $N$ linii vor contine cuvintele din limba ratina, cate un cuvant pe o linie. Mai exact, pe linia $i+1$ este scris cuvantul cu numarul de ordine $i$. Cuvintele sunt formate din litere mici din alfabetul englez. Urmeaza $M$ linii, fiecare linie reprezentand cate o interogare exprimata astfel: primul numar de pe linie este un numar natural $t$ cuprins intre $2$ si $10$ reprezentand numarul de cuvinte din interogare, apoi vor urma cele $t$ numere de ordine ale cuvintelor din interogare, separate prin cate un spatiu.

h2. Date de iesire

...

Fisierul de iesire $ratina.out$ va contine $M$ linii, cate una pentru fiecare interogare din fisierul de intrare. Pe linia $i$ va fi scris gradul de asemanare al cuvintelor din interogarea $i$.

h2. Restrictii

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

* $1 ≤ N ≤ 10000$
* $1 ≤ lungimea maxima a unui cuvant ≤ 2000$
* $1 ≤ suma lungimilor tuturor cuvintelor ≤ 200000$
* $1 ≤ M ≤ 100000$

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

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

| 6 5
  asdf
  asdeffff
  gata
  gara
  pesistem
  pestesistem
  2 1 2
  2 3 4
  2 5 6
  3 1 3 5
  2 1 1
| 3
  2
  3
  0
  4

|
h3. Explicatie

...

Prima interogare cere gradul de asemanare intre cuvintele $asdf$ si $asdeffff$, care este 3 (deoarece cele doua cuvinte au primele 3 litere identice, dar nu si primele 4 litere).
Cea de a doua interogare cere gradul de asemanare intre cuvintele $gata$ si $gara$, care este 2.
Cea de a treia interogare cere gradul de asemanare intre cuvintele $pesistem$ si $pestesistem$ care este 3.
Cea de a patra interogare cere gradul de asemanare intre cuvintele $asdf$, $gata$ si $pesistem$ care este 0.
Ultima interogare este evidenta: un cuvant este $k$-asemenea cu el insusi unde $k$ este chiar lungimea cuvantului.

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

1761