Revizia anterioară Revizia următoare
| 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 lungim$e 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
| jocs.in | jocs.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
