jocs

Jocs

== include(page="template/taskheader" task_id="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.

 
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.

h2. Cerinta

h2. 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.

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.

h2. 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.

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.

h2. 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

* 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
h2. Exemplu
table(example). |_. jocs.in |_. jocs.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 2
18 1
atasarapavamefgefg
18 2
atasarapavamefgefg
|7
1 1
5
13 15
|
 

h3. 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$

== include(page="template/taskfooter" task_id="jocs") ==

5647