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, $\textit{dist}( ``\texttt{abc}", ``\texttt{aaa}") = 2$ (înlocuim caracterul `\texttt{b}' cu `\texttt{a}', respectiv caracterul `\texttt{c}' cu  `\texttt{a}'), iar $\textit{dist}(``\texttt{ABC}", ``\texttt{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 \textit{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=$``\texttt{abc}" subsecvenţele sunt $s(0, 0)=$ ``\texttt{a}", $s(1,1)=$ ``\texttt{b}”, $s(2,2)=$ ``\texttt{c}”, $s(0,1)=$ ``\texttt{ab}",    $s(1,2)=$``\texttt{bc}", $s(0,2)=$``\texttt{abc}", iar pentru şirul $s=$ ``\texttt{aa}" acestea sunt $s(0,0)=$``\texttt{a}", $s(1,1)=$``\texttt{a}", $s(0,1)=$ ``\texttt{aa}".