Levenshteini kaugus

Mida programm teeb

Levenshteini kaugus ütleb, mitu üksiku märgi muudatust (lisa, kustuta, asenda) on vaja, et ühest sõnast saaks teine. Tabeli lahter (i, j) kasutab kolme naabrit: vasakul, üleval ja diagonaalselt. Lõpus kõnnitakse tabelis tagasi ja saadakse muudatuste loend. Seda kasutatakse õigekirja paranduses ("mõtlesid sa ...?"), otsingus ja DNA võrdluses. Sõnad kuni 8 märki.