Skip to content

Instantly share code, notes, and snippets.

@pallid

pallid/РасстояниеЛевенштейн.bsl

Created May 17, 2017 11:10
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save pallid/f5c42ecbf8b0fdaaa79db46759d9d95d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save pallid/f5c42ecbf8b0fdaaa79db46759d9d95d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. pallid created this gist May 17, 2017.
    29 changes: 29 additions & 0 deletions РасстояниеЛевенштейн.bsl
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,29 @@
    Функция РасстояниеЛевенштейна(Строка1, Строка2)

    л1 = СтрДлина(Строка1) + 1;
    л2 = СтрДлина(Строка2) + 1;

    Если л1 = 1 ИЛИ л2 =1 Тогда
    Возврат 449;
    КонецЕсли;

    м = Новый Массив(л1 + 1, л2 + 1);

    Для ы = 0 По л1 Цикл
    м[ы][0] = ы;
    КонецЦикла;

    Для ы = 0 По л2 Цикл
    м[0][ы] = ы;
    КонецЦикла;

    Для ы1 = 1 По л1 Цикл
    Для ы2 = 1 По л2 Цикл
    дифф = Сред(Строка1, ы1, 1) = Сред(Строка2, ы2, 1);
    м[ы1][ы2] = Мин(м[ы1-1][ы2] + 1, м[ы1][ы2-1] + 1, м[ы1-1][ы2-1] + ?(дифф, 0, 1));
    КонецЦикла;
    КонецЦикла;

    Возврат м[л1][л2];

    КонецФункции