Fişierul intrare/ieşire:	jocs.in, jocs.out	Sursă	Lot Sibiu 2011
Autor	Andrei Parvu	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	0.9 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Jocs

Gauss şi Seidel, plictisiţi de activităţile lor cotidiene, s-au apucat de un nou joc. Fiind dat un şir de N caractere şi un număr K, trebuie găsită o subsecvenţă [i, j] a acestuia (adică o submulţime de elemente aflate pe poziţii consecutive) de lungime minimă K, astfel încât numărul de apariţii a subsecvenţei [i, j] în şirul dat plus j – i + 1 să fie maxim.

Cerinta

Fiind dat un şir de N caractere şi un număr natural K, găsiţi pentru acest şir o subsecvenţă cuprinsă între poziţiile [i, j] care maximizează numărul de apariţii a acestei subsecvenţe în şir plus lungimea acesteia, adică j – i + 1.

Date de intrare

Fişierul de intrare jocs.in conţine pe prima linie un număr natural T reprezentând numărul cazurilor de test. Un test este descris prin două linii. Prima linie conţine numerele N şi K cu semnificaţia de mai sus. Pe a doua linie se află N caractere, reprezentând şirul dat.

Date de ieşire

Fisierul de ieşire jocs.out va conţine 2 * T linii, reprezentând răspunsurile pentru cele T teste. Un răspuns se scrie pe două linii: pe prima linie se va scrie numărul de apariţii al subsecvenţei găsite plus lungimea sa, iar pe a doua linie numerele i şi j (i ≤ j) reprezentând capetele subsecvenţei.

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ K ≤ N
• 1 ≤ T ≤ 5
• pentru ca un răspuns sa fie considerat corect, subsecvenţa afişată trebuie sa apară în şirul iniţial de cel puţin 2 ori
• se garantează că pentru fiecare K dat există o soluţie
• în cazul în care există mai multe răspunsuri corecte, puteţi să afişaţi oricare dintre acestea

Exemplu

Explicaţie

Pentru primul caz, litera “a” apare de 6 ori in sir, raspunsul fiind 6 + 1 = 7
Pentru al doilea caz, sirul “efg” apare de 2 ori, raspunsul fiind 2 + 3 = 5

Cum se trimit solutii?