# PBinfo #3655 – Distanta de editare – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Se dau două șiruri de caractere s și t. Asupra șirului s se pot aplica în mod repetat operațiile:


șterge un caracter
inserează un caracter
modifică un caracter

Cerința
Pornind de la șirul s se cere să se obțină șirul t aplicând de un număr minim de ori operațiile date.

Date de intrare
Programul citește de la tastatură șirurile s și t, care se află pe aceeași linie, separate prin spațiu.

Date de ieșire
Programul va afișa pe ecran numărul minim de operații necesar transformării lui s în t..

Restricții și precizări

lungimile celor două șiruri sunt cuprinse între 1 și 100.
șirurile sunt formate numai din litere mari și mici

Exemplu:
Intrare

carte casete
Ieșire

2
Explicație
Cele două operații sunt modificarea lui r în s și inserarea lui e înainte de litera t:
carte -> caste -> casete

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int dp[105][105], n, m;
char s[105], t[105];
int main()
{
    int i, j;
    cin >> (s + 1) >> (t + 1);
    n = strlen(s + 1);
    m = strlen(t + 1);
    /// initializare coloana 0
    for (i = 1; i <= n; i++)
        dp[i][0] = i;
    /// initializare linia 0
    for (j = 1; j <= m; j++)
        dp[0][j] = j;
    /// top-down:
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        dp[i][j] = min({1+dp[i-1][j], 1+dp[i][j-1], dp[i-1][j-1] + (s[i] != t[j])});
    cout << dp[n][m] << "\n";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3655)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3655/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3655/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)