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

Cum finalul semestrului se apropie, este momentul pred\2rii eseului la \b{GCEA} (G\4ndire Critic\2 \3i Etică Academică). Ca orice student conştiincios, ţi-ai pregătit cu atenţie eseul şi ai avut grijă să aibă exact limita minimă admisă. Înainte de corectare, însă, acesta va fi verificat cu ajutorul unui program Anti-Plagiat, iar în cazul în care acesta va detecta prea multe pasaje comune cu cele conţinute de surse publice, va trebui să repeţi materia.

Cum finalul semestrului se apropie, este momentul predării eseului la $GCEA$ (Gândire Critică şi Etică Academică). Ca orice student conştiincios, ţi-ai pregătit cu atenţie eseul şi ai avut grijă să aibă exact limita minimă admisă. Înainte de corectare, însă, acesta va fi verificat cu ajutorul unui program Anti-Plagiat, iar în cazul în care acesta va detecta prea multe pasaje comune cu cele conţinute de surse publice, va trebui să repeţi materia.

Detectorul Anti-Plagiat funcţionează pe un principiu atipic. Pentru fiecare paragraf al textului, acesta va calcula un Scor de Identitate egal cu numărul subsecvenţelor palindromice conţinute de acel paragraf.

Astfel, pentru a minimiza şansele de a fi acuzat de plagiat pe nedrept, eşti interesat de modul optim de a-ţi împărţi lucrarea în paragrafe pentru ca Scorul de Identitate rezultat să fie minim posibil.

Una din multele condiţii ale eseului, însă, este că numărul de paragrafe al acestuia nu poate depăşi un număr prestabilit ${K}$, pentru a nu se pierde din coerenţa ideilor.

Una din multele condiţii ale eseului, însă, este că numărul de paragrafe al acestuia nu poate depăşi un număr prestabilit $k$, pentru a nu se pierde din coerenţa ideilor.

Astfel, dându-se ${N}$-lungimea eseului, ${K}$ şi textul propriu-zis, să se afişeze pentru fiecare ${1}\leq {i}\leq {K}$ Scorul minim de Identitate al textului dacă îl împărţim în ${i}$ paragrafe.

Astfel, dându-se $n$-lungimea eseului, $k$ şi textul propriu-zis, să se afişeze pentru fiecare $1 ≤ i ≤ k$ Scorul minim de Identitate al textului dacă îl împărţim în $i$ paragrafe.

h2. Date de intrare

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

Fişierul de intrare $partmin.in$ va conţine pe prima linie două numere naturale $n$ şi $k$.
 
Pe cea de-a doua linie se va afla un şir de caractere, fără spaţii, format din litere mici ale alfabetului latin ce reprezintă textul eseului.

h2. Date de ieşire

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

În fişierul de ieşire $partmin.out$ se vor afla $k$ linii.
 
Pe linia $i$ a acestuia se va afişa un singur număr natural reprezentând costul minim de a împărţi eseul in $i$ paragrafe.

h2. Restricţii

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

* O subsecvenţă a unui şir este formată din caractere aflate pe poziţii consecutive în şir.
* Un paragraf al eseului trebuie să reprezinte o subsecvenţă nevidă a acestuia.
* Toate paragrafele sunt disjuncte, iar reuniunea lor este egală cu textul complet.
* k ≤ n pentru orice test.
* Pentru teste ce valorează $10$ puncte: $k ≤ n ≤ 100$
* Pentru alte teste ce valorează $10$ puncte: $2 ≤ n ≤ 1000$ şi $k=2$
* Pentru alte teste ce valorează $10$ puncte: $k ≤ n ≤ 1000$ şi toate caracterele şirului sunt egale.
* Pentru restul testelor $k ≤ n ≤ 1000$
 

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

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

| 5 2
  axaxy
| 7
  5

|
h3. Explicaţie

...

Dacă vom lăsa tot textul într-un singur paragraf, acesta va conţine subsecvenţele palindromice:
 
$"a"$, $"x"$, $"a"$, $"x"$, $"y"$, $"axa"$ şi $"xax"$.
 
Pentru două paragrafe putem împărţi textul în: $"ax"$ şi $"axy"$ ce vor conţine doar cele $5$ subsecvenţe palindromice formate dintr-un singur caracter.

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