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=(A1,A2...AN) de cuvinte
este mai mic decat un set B=(B1,B2...BN)daca
exista o pozitie 1
<= i <= N astfel incat
A1=B1,
A2=B2 ... Ai-1=Bi-1 si Ai<Bi.
Exemple
cuvinte.in
cuvinte.out
Explicatie
aAaAbAbAbBbB
3
aA
bA
bB
O alta solutie,
mai mare din punct de vedere lexicografic, este: aA
bB Ab
pQpQ
1 pQ
LoL
2 oL Lo
Mircea Paşoi Universitatea Bucuresti,
Facultatea de Matematica si Informatica mircea@infoarena.ro