edist

Edist

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

Poveste şi cerinţă...

Fie un şir oarecare de caractere. Asupra lui definim următoarele 3 operaţii:
 
* *inserare*: pe o poziţie oarecare se adauga un caracter oarecare
* *ştergere*: se şterge caracterul de pe o poziţie oarecare din şir
* *înlocuire*: se înlocuieşte caracterul de pe o poziţie oarecare din şir cu orice alt caracter.
 
Se dau două şiruri $S1$ si $S2$ conţinând doar litere mici ale alfabetului englez şi având $N$ şi, respectiv, $M$ caractere. Distanţa de editare a celor două şiruri este numărul minim de operaţii definite mai sus ce trebuie aplicat asupra primului şir pentru a-l transforma în cel de-al doilea şir. Acelaşi tip de operaţie poate fi aplicat de mai multe ori. Aflaţi distanţa de editare a celor doua şiruri, ştiind că aceasta este mai mică sau egală cu un număr întreg $K$ dat.

h2. Date de intrare

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

Pe prima linie a fişierului de intrare $edist.in$ se afla trei numere întregi: $N$, $M$ şi $K$. Pe a doua linia a fişierului se află $N$ litere mici din alfabetul englez reprezentând şirul $S1$. Pe a treia linie a fişierului se află $M$ litere mici din alfabetul englez ce reprezintă şirul $S2$.

h2. Date de ieşire

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

În fişierul de ieşire $edist.out$ se va afla un singur număr întreg reprezentând distanţa de editare a celor doua şiruri.

h2. Restricţii

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

* $1 ≤ N, M ≤ 20 000$
* $1 ≤ K ≤ 500$
* Pentru $70%$ din teste $N, M ≤ 2 000$.

h2. Exemplu

| 5 6 5
harpa
armura

| 4
|

| 4 |
| 5 5 4
carte
antet
| 3
|

h3. Explicaţie

...

O posibilă modalitate de a transforma şirul $harpa$ în $armura$ folosind $4$ operaţii este:
 
1. ştergem litera $h$ din primul şir,
2. înlocuim litera $p$ cu litera $m$,
3. adăugăm litera $u$ înainte de ultima literă din primul şir,
4. adăugăm litera $r$ înainte de ultima literă din primul şir.

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

6121