Википедија

Левенштајново растојање — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Ред 55:
=== Итеративно са целом матрицом ===
Израчунавање Левенштајновог растојања је базирано на запажању да ако резервишемо матрицу за чување растојања између свих префикса прве ниске и свих префикса друге, онда можемо да израчунамо вредности у матрици помоћу динамичког програмирања и тако нађемо растојање између два пуне ниске.
Овај алгоритам је пример "одоздо„одоздо на горе"горе“ динамичког програмирања, као што је дискутовано, са варијацима, 1974. године у ''The [[String-to-string correction problem]]'' од Robert A. Wagner and Michael J. Fischer.<ref>{{citation |first=Robert A. |last=Wagner |first2=Michael J. |last2=Fischer |author2-link=Michael J. Fischer |title=The String-to-String Correction Problem |journal=Journal of the ACM |volume=21 |issue=1 |year=1974|pages=168-173 |doi= 10.1145/321796.321811}}</ref>
Имплементација функције Леванштајновог растојања која узима две ниске, „с“ дужине “м“ и ниску „т“ дужине „н“ и враћа Левенштајново растојање између та две ниске.
<source lang="C">
Преузето из „https://sr.wikipedia.org/wiki/Левенштајново_растојање”