Raci

raci

== include(page="template/taskheader" task_id="raci") ==

_Antoniei îi plac foarte mult crustaceele. Fiindcă lui Antonio îi este imposibil să îi ofere acesteia un rac drept cadou, s-a gândit să numească această problemă... Raci_
 
Se dă un număr $N$ şi $N$ cuvinte formate doar din litere mici ale alfabetului englez.
 
h2. Cerinţă
 
Să se calculeze cel mai lung subşir de cuvinte din şirul iniţial ce respectă următoarele proprietăţi :
 
* Pentru orice $i$ , $1 ≤ i ≤ M-1$ , ultimul caracter al lui $C{~i~}$ este egal cu primul caracter al lui $C{~i+1~}$
* Pentru orice $i$ , $1 ≤ i ≤ M-1$ , $P{~i+1~} - P{~i~} ≤ K$ , pentru un $K$ dat
 
Unde $M$ este lungimea noului şir rezultat , $C{~i~}$ este cuvântul aflat pe poziţia $i$ în noul şir şi $P{~i~}$ este poziţia pe care se află cuvântul $C{~i~}$ în şirul iniţial.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $raci.in$ va conţine pe prima linie două valori $N$ şi $K$ cu semnificaţia din enunţ.
Pe a doua linie din fişier se vor afla cele $N$ cuvinte separate între ele prin exact un spaţiu.

Fişierul de intrare $raci.in$ ...

h2. Date de ieşire

În fişierul de ieşire $raci.out$ se va afişa o singură valoare reprezentând lungimea celui mai lung subşir de cuvinte care respectă cele două proprietăţi specificate în enunţ.

În fişierul de ieşire $raci.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 500 000$
* $1 ≤ K ≤ N$
* $2 ≤ lungimea oricărui cuvânt ≤ 10$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. raci.in |_. raci.out |

| 11 3
  aa ab bc dd db be ff fg eh gi hj
| 5
|

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

h3. Explicaţie

Cel mai lung subşir este: $aa ab bc **dd** **db** **be** ff fg **eh** gi **hj**$ .

...

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

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

10158