Fişierul intrare/ieşire:pentagrame.in, pentagrame.outSursăTabăra ICHB 2012, Ziua 1, Grupa 2
AutorDan Constantin SpatarelAdăugată despatarelDan-Constantin Spatarel spatarel
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pentagrame

Walter vrea să-i ajute pe Nikita şi Michael să se întâlnească fără ştirea conducerii Secţiunii, aşa că s-a oferit să facă treaba Nikitei, în locul ei. Când să se pună pe treabă, a fost însărcinat să construiască o nouă bombă de mare putere.

Văzându-se în dificultate, l-a rugat pe Birkhoff să-l ajute, dar Birkhoff l-a refuzat, pentru că tocmai a fost ameninţat de Michael şi acum lucrează pentru el.

Lipsit de alternative, Walter v-a rugat pe voi să faceţi treaba Nikitei.

Nikita studiază mesajele codificare pe care membrii Celulei Roşii le-au transmis între ei prin radio în ultima sa misiune. În cercetările ei, ea a găsit în baza de date a Secţiunii o listă de pentagrame copiată cu câteva luni în urmă, în mod secret, din serverele Celulei Roşii.

Nikita crede că poate decodifica mesajele pe care şi le-au transmis teroriştii dacă identifică pentagramele care apar în cele mai multe dintre cuvinte ca subsecvenţe.

Date de intrare

Fişierul de intrare pentagrame.in conţine pe prima linie două numere naturale N şi M, reprezentând numărul de pentagrame copiate respectiv numărul de mesaje codificate.
Pe fiecare din următoarele N linii se va găsi câte o pentagramă (un şir de exact 5 litere mici ale alfabetului englez sau cifre).
Pe fiecare din următoarele M linii se va găsi câte un mesaj codificat (un şir de litere mici ale alfabetului englez sau cifre).

Date de ieşire

În fişierul de ieşire pentagrame.out se va găsi pe prima linie un număr natural X reprezentând numărul de pentagrame care apar în cele mai multe mesaje ca subsecvenţe iar pe următoarele X linii se vor regăsi pentagramele cerute, câte una pe linie, în ordine lexicografică.

Restricţii

  • 1 ≤ N ≤ 50 000
  • 1 ≤ M ≤ 50 000
  • Pentagramele sunt distincte două câte două.
  • Lungimea unui mesaj codificat este de cel puţin 5 caractere şi cel mult 30.
  • În ordine lexicografică, cifrele sunt înaintea literelor mici ale alfabetului englez.

Exemplu

pentagrame.inpentagrame.out
3 5
n4isl
4hd72
k3j4h
id8k3j4hd728o0
n4isln4isln4isl
kk7gud589hylo9
4hd72
idiodk3j4howoi82
2
4hd72
k3j4h

Explicaţie

Cele 3 pentagrame se regăsesc în mesajele teroriştilor astfel:
id8k3j4hd728o0
n4isln4isln4isl
kk7gud589hylo9
4hd72
idiodk3j4howoi82

Deşi pentagrama n4isl apare de 3 ori într-un mesaj, ea apare într-un singur mesaj şi nu este cea mai frecventă, deoarece celelalte două pentagrame apar în două mesaje fiecare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?