repeat

Sa consideram un sir de caractere T si k un numar natural nenul.

Cerinta

Sa se determine o subsecventa a sirului T, formata din k caractere consecutive, care se repeta în sir de un numar maxim de ori.

Date de intrare

Fisierul de intrare repeat.in contine doua linii. Pe prima linie este scris sirul T, iar pe cea de a doua linie numarul natural k.

Date de iesire

Fisierul de iesire repeat.out va contine doua linii. Pe prima linie se va scrie un numar natural Rmax care reprezinta numarul maxim de repetari in sirul T ale unei subsecvente de lungime k. Pe cea de a doua linie se va scrie pozitia de inceput a unei subsecvente de lungime k care se repeta in sir de Rmax ori. Dintre toate pozitiile de inceput posibile va fi afisate cea minima.

Restrictii si precizari

0 < k <= 500
Sirul T este format din maxim 100 000 litere mici ale alfabetului englez.
Doua aparitii distincte ale subsecventei se pot suprapune partial.
Pozitiile in sirul T sunt numerotate incepand cu 1.

Exemplu

repeat.in	repeat.out	Explicatie
ababacabac 3	3 1	Subsecventa de lungime 3 aba se repeta de un numar maxim de ori (3). Pozitia de inceput minima este 1.

Timp maxim de executie/test: 2 secunde

prof. Marinel Serban
Liceul de Informatica "Grigore Moisil" Iasi
Contact:marinel_serban@yahoo.com