cuvinte

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.

Cerinta

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 cuvinte.in se va gasi sirul S.

Date de iesire

Prima linie a fisierului cuvinte.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.

Exemple

Timp maxim de executie/test: 0.2 secunde

Mircea Paşoi
Universitatea Bucuresti, Facultatea de Matematica si Informatica
mircea@infoarena.ro