Rezolvare PBinfo #3765

Un laborator specializat studiază mutațiile unui virus pandemic pentru a găsi cel mai bun vaccin pentru combaterea acestuia. Codul unui virus este un șir format din litere (mari și mici) ale alfabetului englez. Numim mutație a virusului pandemic un șir de caractere care are aceeași lungime cu codul virusului și care conține o singură poziție pentru care litera din șir este diferită de litera situată pe poziția respectivă în codul virusului pandemic. De exemplu, pentru virusul pandemic având codul abac, șirul Bbac reprezintă o mutație, deoarece are aceeași lungime și diferă doar prin litera de pe prima poziție. Laboratorul primește o listă conținând codurilor mai multor viruși descoperiți în urma testărilor.

Cerința

Scrieți un program care, cunoscând codul virusului pandemic și lista codurilor virușilor descoperiți în urma testărilor, rezolvă următoarele cerințe:

1. Determină numărul de mutații ale virusului pandemic existente în listă, mutații nu neapărat distincte;
2. Determină mutația cu număr maxim de apariții în listă; dacă există mai multe mutații cu același număr maxim de apariții, se va determina prima mutație, în ordine lexicografică.

Date de intrare

Fișierul de intrare virus.in conține pe prima linie un număr natural C reprezentând cerința care trebuie să fie rezolvată (1 sau 2). Pe cea de a doua linie se află codul virusului pandemic. Pe a treia linie se află un număr natural N, reprezentând numărul de viruși existenți în lista primită de laborator. Pe următoarele N linii se află codurile virușilor din listă, câte un cod pe o linie.

Date de ieșire

Fișierul de ieșire virus.out va conține o singură linie:

• Dacă C = 1, pe prima linie va fi scris un număr natural care reprezintă câte elemente din listă sunt mutații ale virusului pandemic.
• Dacă C = 2, pe prima linie va fi scris un șir de caractere care reprezintă mutația cu număr maxim de apariții. Dacă există mai multe mutații cu număr maxim de apariții, va fi afișată prima (cea mai mică), în ordine lexicografică.

Restricții și precizări

• 2 ≤ N ≤ 50.000
• Lungimea maximă a codului unui virus este 200
• Daca a și b sunt două șiruri de lungime lg, spunem că șirul a = a0 a1 a2 ... alg-1 este mai mic din punct de vedere lexicografic decât șirul b = b0 b1 b2 ... blg-1, dacă există o poziție k ∈{0, 1, ..., lg - 1} astfel încât ai = bi pentru orice 0 ≤ i < k și ak < bk.
• În codul ASCII codurile literelor mari sunt mai mici decât codurile literelor mici.

Exemplul 1:

virus.in

1
abac
5
Abbbq
Zbac
abbC
aBac
Zbac

virus.out

3

Explicație

Mutațiile sunt Zbac, aBac și Zbac.

Exemplul 2:

virus.in

2
abcD
8
abcdD
XbcD
Xc
XbcD
aXcD
aXcD
aXc
ab

virus.out

XbcD

Explicație

Mutațiile XbcD și aXcD apar fiecare de câte 2 ori, prima în ordine lexicografică fiind XbcD. XbcD este mai mic lexicografic decât aXcD, deoarece în codul ASCII: 'A' < 'B' < ... < 'Z' < 'a' < 'b' < ... < 'z'