ID #123 · Colecția InfoAs · Operatori și expresii

Problema Distanta de editare

Distanța de editare (numită și _Distanță Levenshtein_ sau, în engleză, _Edit distance_) dintre două șiruri de caractere `s` și `t` reprezintă numărul minim de operații de inserare a unui caracter, ștergerea unui caracter sau modificarea (substituirea) unui caracter aplicate șirului `s` pentru a obține șirul `t` (sau invers, pentru că operația este comutativă). ## Cerință Se dau două șiruri de caractere `s` și `t`, formate doar din litere mici ale alfabetului englez. Asupra lui `s` se pot aplica oricare dintre următoarele operații, în mod repetat: * inserarea unui caracter, pe orice poziție; * ștergerea unui caracter, de pe orice poziție; * modificarea (substituirea) unui caracter, de pe orice poziție. Să se determine numărul minim de operații necesare pentru a transforma șirul `s` în șirul `t`. ## Date de intrare Programul citește de la tastatură, de pe prima linie, șirul `s`, iar de pe a doua linie, șirul `t`. ## Date de ieșire Programul afișează pe ecran un singur număr, reprezentând distanța de editare a șirurilor `s` și `t` (numărul minim de operații necesare pentru a transforma șirul `s` în șirul `t`). ## Restricții și precizări * `1 ≤ lungimile șirurilor ≤ 255`