Cora

Time limit: 0.02s Memory limit: 40MB Input: cora.in Output: cora.out

Amidamaru iubește să-și facă cumpărăturile la Cora. Fiind magazinul lui preferat, și-a făcut o listă cu toate produsele pe care le cumpără de obicei, reprezentate prin nn cuvinte.

Cum Amidamaru este un om bine organizat, a rugat-o pe mama lui să îi facă o listă completă de cumpărături pentru ziua de azi, listă în care se găsesc produse din cele nn, fiecare putând să apară de mai multe ori. Lista trimisă de mama lui s-a stricat când Amidamaru a primit-o pe telefon, spațiile au dispărut, unele caractere s-au schimbat, iar acum lista e un șir aleator de caractere SS.

Ajută-l pe Amidamaru să recupereze produsele care încă se mai găsesc pe listă, aflând pentru fiecare din cele nn cuvinte de câte ori apare în șirul de caractere SS care reprezintă lista amestecată și apoi afișând produsul cu cele mai multe apariții.

Cerință

Cunoscând nn și SS, determinați cuvântul cu cele mai multe apariții în SS.

Date de intrare

Pe prima linie a fișierului de intrare cora.in se găsește SS, șirul de caractere.
Pe cea de-a doua linie, se găsește un număr întreg, nn.
Pe următoarele nn linii se găsesc cele nn cuvinte ca și șiruri de caractere, reprezentând produsele lui Amidamaru.

Date de ieșire

Pe prima linie a fișierului de ieșire cora.out se va găsi un singur număr întreg, reprezentând numărul maxim de apariții ale unui produs.
Pe cea de-a doua linie se va afișa numele produsului cu număr maxim de apariții. În cazul în care există mai multe soluții, se va afișa produsul cu numele cel mai mic din punct de vedere lexicografic.

Restricții și precizări

  • 11 \leq Lungimea lui S1 000 000S \leq 1 \ 000 \ 000;
  • 11 \leq Lungimea unui cuvânt 10 000\leq 10 \ 000;
  • 1n1001 \leq n \leq 100;
  • Un cuvânt poate apărea în listă doar pe poziții consecutive ale șirului;
  • Toate cuvintele sunt formate din caractere mici ale alfabetului englez.

Exemplul 1

cora.in

merepereshajdsperesscajubanan
4
mere
pere
banane
caju

cora.out

2
pere

Explicație

În exemplu, mere apare o singură dată, pere de 22 ori, caju o singură dată, iar banane deloc. pere este produsul cu număr maxim de apariții.

Exemplul 2

cora.in

primetescojhdftescoffdtescogatoruhuadeprimeprimescoprime
4
gatorade
prime
tesco
sco

cora.out

4
prime

Explicație

prime și sco apar amândouă de exact 44 ori, dar prime este mai mic lexicografic.

Log in or sign up to be able to send submissions!