cuvinte3

Cuvinte 3

== include(page="template/taskheader" task_id="cuvinte3") ==

Poveste si cerinta...

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$.

h2. Date de intrare

Fisierul de intrare $cuvinte3.in$ ...

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

h2. Date de iesire

In fisierul de iesire $cuvinte3.out$ ...

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.

h2. 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{~1~},A{~2~}...A{~N~})$ de cuvinte este mai mic decat un set $B=(B{~1~},B{~2~}...B{~N~})$ daca exista o pozitie $1 &le; i &le; N$ astfel incat $A{~1~}=B{~1~}, A{~2~}=B{~2~} ... A{~i-1~}=B{~i-1~}$ si $A{~i~}<B{~i~}$.

h2. Exemplu
table(example). |_. cuvinte3.in |_. cuvinte3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| aAaAbAbAbBbB
| 3
aA
bA
bB |
| pQpQ
| 1
pQ |
| LoL
| 2
oL
Lo |

h3. Explicatie

...

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

== include(page="template/taskfooter" task_id="cuvinte3") ==

2951