| Fişierul intrare/ieşire: | edist.in, edist.out | Sursă | Selectie Girls Programming Camp |
| Autor | Paul-Dan Baltescu | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Edist
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.
Date de intrare
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.
Date de ieşire
Î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.
Restricţii
- 1 ≤ N, M ≤ 20 000
- 1 ≤ K ≤ 500
- Pentru 70% din teste N, M ≤ 2 000.
Exemplu
| edist.in | edist.out |
|---|---|
| 5 6 5 harpa armura | 4 |
| 5 5 4 carte antet | 3 |
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.
