== 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
table(example). |_. edist.in |_. edist.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 5 6 5
harpa
armura
| 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") ==
