Definim $distanţa$ dintre două şiruri de caractere de aceeaşi lungime ca fiind numărul minim de caractere ce trebuie modificate (înlocuite fiecare cu câte un alt caracter) în primul şir pentru a obţine al doilea şir. Vom nota distanţa dintre şirurile $a$ şi $b$ cu $dist(a, b)$.

De exemplu, $dist(abc, aaa) = 2$ (înlocuim caracterul $b$ cu $a$, respectiv caracterul $c$ cu  $a$), iar $dist(ABC, abc) = 3$ (literele mici se consideră diferite de cele mari).

De exemplu, $dist(abc, aaa) = 2$ (înlocuim caracterul $b$ cu $a$, respectiv caracterul $c$ cu {$a$}), iar $dist(ABC, abc) = 3$ (literele mici se consideră diferite de cele mari).

Definim o $subsecvenţă$ a unui şir $s$ de caractere ca fiind un şir format din caractere de pe poziţii consecutive din $s$. Considerăm două subsecvenţe ca fiind distincte dacă încep sau se termină la poziţii diferite. Vom nota cu $s(i, j)$ subsecvenţa formată din caracterele indexate de la $i$ la $j$ ale şirului $s$. Şirurile se indexează de la 0. Exemplu: pentru şirul $s = abc$ subsecvenţele sunt $s(0, 0) = a, s(1,1) = b, s(2,2) = c, s(0,1) = ab, s(1,2) = bc, s(0,2) = abc$, iar pentru şirul $s=$ aa acestea sunt $s(0,0) = a, s(1,1) = a, s(0,1) = aa$.