Limba ratină are doar N cuvinte, numerotate de la 1 la N. Două sau mai multe cuvinte se numesc k-asemenea dacă au primele k litere identice.
Gradul de asemănare între t cuvinte este k dacă cele t cuvinte sunt k-asemenea, dar nu sunt (k+1)-asemenea.
Cerinţă
Scrieţi un program care pentru un set de t cuvinte dat, răspunde la interogări de genul: ″Care este gradul de asemănare între cuvintele x1 x2 ... xt″ ?
Date de intrare
Fişierul de intrare ratina.in va conţine pe prima linie două numere naturale N M, separate printr-un spaţiu, reprezentând numărul de cuvinte din limba ratină, respectiv numărul de interogări.
Următoarele N linii vor conţine cuvintele din limba ratină, câte un cuvânt pe o linie. Mai exact, pe linia i+1 este scris cuvântul cu numărul de ordine i. Cuvintele sunt formate din litere mici din alfabetul englez.
Urmează M linii, fiecare linie reprezentând câte o interogare exprimată astfel: primul număr de pe linie este un număr natural t cuprins între 2 şi 10 reprezentând numărul de cuvinte din interogare, apoi vor urma cele t numere de ordine ale cuvintelor din interogare, separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire ratina.out va conţine M linii, câte una pentru fiecare interogare din fişierul de intrare. Pe linia i va fi scris gradul de asemănare al cuvintelor din interogarea i.
Restricţii
0 < N < 10 001
0 < lungimea maximă a unui cuvânt < 2000
0 < suma lungimilor tuturor cuvintelor < 200 000
1 < M < 100 001
Pentru teste cu N ≤ 200, se acordă 50 de puncte din care 30 de puncte pentru teste şi cu M ≤ 10000.
Prima interogare cere gradul de asemănare între cuvintele asdf şi asdeffff, care este 3 (deoarece cele două cuvinte au primele 3 litere identice, dar nu şi primele 4 litere).
Cea de a doua interogare cere gradul de asemănare între cuvintele gata şi gara, care este 2.
Cea de a treia interogare cere gradul de asemănare între cuvintele pesistem şi pestesistem care este 3.
Cea de a patra interogare cere gradul de asemănare între cuvintele asdf, gata şi pesistem care este 0.
Ultima interogare este evidentă: un cuvânt este k-asemenea cu el însuşi unde k este chiar lungimea cuvântului.