| Fişierul intrare/ieşire: | frequent.in, frequent.out | Sursă | RMI 2016 |
| Autor | Catalin Francu | Adăugată de |  Vlad Dumitru-Popescu •depevlad |
| Timp execuţie pe test | 1 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
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.
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.
Output:
Î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.
Restrictii:
- 2 ≤ N ≤ 200,000
- 2 ≤ K ≤ N
Subtaskuri:
- Testele vor fi punctate individual.
- Subtask 1 (30%): N ≤ 10,000
- Subtask 2 (40%): N ≤ 100,000
- Subtask 3 (30%): Limite initiale.
Exemplu si explicatie:
| 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 |
