Adrian are toate motivele sa fie multumit. De cand s-a imprietenit
cu Laura, totul ii merge bine. A scris chiar si un mic roman, despre dragoste
si eroism. Se gandeste ca poate il va publica intr-o zi.
Astazi insa nu este in apele lui. Prietena lui, dupa ce i-a citit romanul, i-a
spus:
"- Dragul meu, sunt incantata. Scrii frumos si ai talent. Totusi, m-am gandit
sa-ti spun, ca in timpul lecturii, am avut acel sentiment de "deja vu". Mai
exact, uneori impresia mea era, ca citeam acelasi fragment pentru a doua oara,
iar unele fraze se repetau chiar de mai multe ori in textul romanului. Nu as
putea sa-ti indic acele fraze, pentru ca nu mi-am notat, insa sunt sigura ca
nu ma insel".
Adrian este convins ca Laura are dreptate. Pentru a indrepta aceste neajunsuri,
el doreste sa identifice sirurile de caractere care se repeta in text si sa
localizeze pozitiile acestora.
Cerinta
Identificati pentru Adrian, sirul de caractere de lungime
maxima, care se repeta de cel putin
K ori in textul romanului.
Date de intrare
Fisierul novel.in
are pe prima linie numarul natural
K. Pe liniile urmatoare, incepand cu linia a doua, se afla textul romanului.
Date de iesire
Fisierul novel.out
va avea pe prima linie numerele naturale
L si N, separate printr-un
singur spatiu, reprezentand lungimea maxima a secventei care se repeta de cel
putin K ori, respectiv numarul
real de repetari.
Pe linia a doua, separate prin cate un spatiu, se vor afisa numerele
I0 I1 ... IN reprezentand pozitiile
de inceput ale fiecareia dintre cele
N + 1 secvente identice de lungime
L.
Incepand cu linia a treia, se va afisa sirul de caractere de lungime maxima
care se repeta de cel putin K
ori. Dupa afisarea sirului de caractere nu se va scrie caracterul de sfarsit
de linie (newline).
Restrictii si precizari
1 <= Numarul de caractere
din fisierul de intrare <= 30000
1 <= K, N <= 300
Se contorizeaza toate caracterele din fisierul de intrare, chiar si cele
negrafice.
Sirul de caractere care se repeta poate sa includa oricare dintre caracterele
din fisier.
Pozitia fiecarui caracter, se calculeaza in raport cu primul caracter al
romanului, care este situat pe pozitia 0
Numarul de repetari, se socoteste incepand cu cea de-a doua aparitie a secventei
in text.
Daca problema are mai multe solutii, se afiseaza doar solutia referitoare
la fraza repetitiva cea mai mica in ordine lexicografica.
Pentru datele de test exista intotdeauna solutie.
Exemplu
novel.in
novel.out
Explicatie
1 Now I feel, like I've been
to heaven and back 100 times
Every time I look in her eyes
Yes, I feel, like I've been
to heaven and back 100 times I look deep in her light brown eyes
and I loved her
Why, why, oh, me
Why couldn't she see
that I loved her so much
God, I love to look in her eyes...
And I feel, like I've been
to heaven and back 100 times Yes, I feel...
53 2
3 90 296
I feel, like I've been
to heaven and back 100 times
Sirul de caractere
de lungime maxima care se repeta cel putin o data, are 53 de caractere
si apare de trei ori in text, deci se repeta de 2 ori. Acesta este: I feel, like I've been
to heaven and back 100 times
3
90 si 296
sunt pozitiile primului caracter al secventei, raportate la pozitia
primului caracter, 'N',
al textului. Primul caracter al secventei este spatiu, iar ultimul
este newline.