frequent

Frequent

Un astrobiolog studiaza viata pe planeta Alphabet. Pe aceasta planeta, materialul genetic al vietii are 26 de nucleotide. Asadar, genomul oricarei vietuitoare de pe planeta poate fi reprezentat ca un sir de litere mici, din alfabetul latin. Astrobiologul a determinat ADN-ul a *$K$* forme de viata, nu necesar distincte, cu o lungime totala de *$N$* nucleotide. Acum, ea doreste sa gaseasca subsecvente de ADN care sa apara des in codul genetic al acestor forme de viata. Fie *$L(i)$* cea mai lunga subsecventa de nucleotide consecutive care apare in cel putin *$i$* dintre formele de viata, pentru *$2 ≤ i ≤ K$*. Observati ca *$L(i)$* poate fi chiar si *$0$*. Datoria voastra este sa ajutati astrobiologul sa calculeze sirul *$L$*.

h2. Date de intrare

h2. Input:

Fişierul de intrare $frequent.in$ contine pe prima linie un numar intreg *$K$*, reprezentand numarul formelor de viata. Fiecare dintre urmatoarele *$K$* linii contine un sir nevid de litere mici ale alfabetului latin, sirul cu indicele *$i$* reprezentand codul genetic al fiintei *$i$*. Fiecare sir este urmat de caracterul $newline$.

h2. Date de ieşire

h2. Output:

În fişierul de ieşire $frequent.out$ se vor gasi *$K - 1$* linii, reprezentand valorile *$L(2), L(3), ..., L(n)$*, cate una pe fiecare linie.

În fişierul de ieşire $frequent.out$ se vor gasi *$K - 1$* linii, reprezentand valorile *$L(2), L(3), ..., L(K)$*, cate una pe fiecare linie.

h2. Restricţii si precizari

h2. Restrictii:

* $2 ≤ N ≤ 200,000$
* $2 ≤ K ≤ N$

h2. Subtaskuri

h2. Subtaskuri:

* *Testele vor fi punctate individual.*

* Sub
 
 
h2. Exemplu
 
table(example). |_. frequent.in |_. frequent.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

* Subtask 1 (30%): $N ≤ 10,000$
* Subtask 2 (40%): $N ≤ 100,000$
* Subtask 3 (30%): $Limite initiale.$
 
h2. Exemplu si explicatie:
 
table(example). |_. frequent.in |_. frequent.out |_. Explicatie |
| 6
matter
animate
pattern
thermal
domain
teammate
| 5
3
2
2
1 | _atter_ apare in doua dintre siruri.
_mat_ apare in trei dintre siruri.
_ma_ (sau _at_ sau _te_) apar in patru dintre siruri.
_ma_ apare in cinci dintre siruri.
_a_ apare in toate sirurile |

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