Date due liste L1 e L2 di caratteri – per esempio L1= [r,i,s,o,t,t,o] e L2= [p,r,e,s,t,o] – si definisce distanza di L1 da L2 il numero minimo di “mosse” da eseguire su L1 per renderla uguale a L2, dove ogni mossa può essere una delle seguenti tre operazioni:
- sostituzione di un carattere di L1 con altro carattere;
- inserimento di un nuovo carattere in L1;
- cancellazione di un carattere di L1.
Ad esempio, L1 può essere trasformata in L2 con 13 mosse: infatti con 7 cancellazioni, L1 diventa uguale alla lista vuota [ ] e con 6 inserimenti successivi (dei 6 caratteri p r e s t o) la lista vuota diventa uguale a L2.
Ma L1 può essere trasformata in L2 anche con solo 4 mosse: inserendo in prima posizione il carattere p, sostituendo il carattere i con il carattere e, cancellando il primo carattere o e uno dei due caratteri t.
La distanza di L1 da L2 è quindi 4.Trovare la distanza D tra le due liste L1=[r,p,a,l,z,m,g] e L2=[b,r,x,a,m,g].