Fişierul intrare/ieşire:ratina.in, ratina.outSursăONI 2006
AutorDan-Ionut FecheteAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ratina

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.

Cerinta

Scrieti un program care pentru un set de t cuvinte dat, raspunde la interogari de genul: "Care este gradul de asemanare intre cuvintele x1 x2 ... xt" ?

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.

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.

Restrictii

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

Exemplu

ratina.inratina.out
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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content