Fişierul intrare/ieşire:	cuvinte3.in, cuvinte3.out	Sursă	.campion 2008, Runda 12
Autor	Mircea Bogdan Pasoi	Adăugată de	Mircea Pasoi •domino
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cuvinte 3

Fie C o multime de cuvinte, toate de o lungime fixa L. Spunem ca un sir de caractere S poate fi scris folosind multimea de cuvinte C, daca pentru orice caracter din S exista o secventa de L caractere din S, care este un cuvant din C si care contine caracterul respectiv.
Se da un sir de caractere S format numai din litere din alfabetul englez, in care marimea literelor alterneaza (Exemple: aBcDeF, AbCd). Sa se determine o multime C de cardinal minim care contine numai cuvinte de lungime 2, multime cu care poate fi scris sirul S.

Date de intrare

Pe prima linie a fisierului de intrare cuvinte3.in se va gasi sirul S.

Date de iesire

Prima linie a fisierului cuvinte3.out va contine un singur numar natural min reprezentand cardinalul minim al multimii C. Urmatoarele min linii vor contine cate un cuvant de lungime 2 din multimea C determinata. Cuvintele se vor afisa in ordine alfabetica.

Restrictii

• Lungimea sirului S este mai mica sau egala cu 100 000
• Se considera ca a < b < ... < z < A < B < ... < Z
• C, fiind o multime, va fi formata numai din cuvinte distincte
• Daca exista mai multe seturi de cardinal minim se va afisa acela care este minim lexicografic. Spunem ca un set A=(A₁,A₂...A_N) de cuvinte este mai mic decat un set B=(B₁,B₂...B_N) daca exista o pozitie 1 ≤ i ≤ N astfel incat A₁=B₁, A₂=B₂ ... A_i-1=B_i-1 si A_i<B_i.

Exemplu

Explicatie

Pentru primul test, o alta solutie, mai mare din punct de vedere lexicografic, este:
aA
bB
Ab

Cum se trimit solutii?