Fişierul intrare/ieşire:	sabin.in, sabin.out	Sursă	ONI 2015, Baraj
Autor	Andrei Ciocan, Andrei Parvu, Eugenie Daniel Posdarascu, Vlad Ionescu	Adăugată de	Tudor Tiplea •tzipleatud
Timp execuţie pe test	0.75 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sabin

<>p. Dat fiind ca mallu' nu era cea mai apropiată locaţie, Sabin s-a hotărât să petreacă ceva timp la bibliotecă. Aici el a dat peste două rafturi cu cărţi.

<>p. Primul raft conţine N compartimente de cărţi, fiecare compartiment având acelaşi număr de
cărţi, K. Cel de-al doilea raft conţine un singur compartiment cu M cărţi. Toate cărţile din ambele rafturi au titlurile formate din exact P caractere mici ale alfabetului englez.

<>p. Un prefix al unui şir de caractere se defineşte ca o subsecvenţă a şirului care începe de pe prima poziţie a acestuia. Definim cel mai mare prefix comun (maxprefix) a două şiruri de caractere ca fiind lungimea celei mai lungi secvenţe de caractere care este prefix şi al primului şir şi al celui de-al doilea.

<>p. Fiind date două compartimente de titluri de cărti A = [c1, c2, ..., cK] şi B = [d1, d2, .., dK] definim gradul de similitudine al acestora ca fiind min(maxprefix(c1, d1), maxprefix(c2, d2), …, maxprefix(cK, dK)).

<>p. Sabin ar dori să scoată K cărţi din al doilea raft şi să găsească un compartiment din primul raft pentru care gradul de similitudine să aibă o valoare dată.

<>p. Ca să intraţi în graţiile lui Sabin având la dispozitie cele două rafuri de cărţi, trebuie să răspundeţi la Q întrebări de forma: “Fiind date K cărţi din al doilea raft, găsiţi toate compartimentele din primul raft care au gradul de similitudine cu compartimentul dat exact X şi afişaţi numărul lor”.

Date de intrare

Fişierul de intrare sabin.in ...

Date de ieşire

În fişierul de ieşire sabin.out ...

Restricţii

• ... ≤ ... ≤ ...

Exemplu

Explicaţie

...

Cum se trimit solutii?