Я недавноопубликовал вопрос об оптимизации алгоритма для вычисления расстояния Левенштейна, и ответы привели меня к статье в Википедии оРасстояние Левенштейна.

В статье упоминается, что если есть ограничениеk на максимальном расстоянии возможный результат может быть от данного запроса, тогда время выполнения может быть уменьшено сО (млн) вO (кН), m а такжеn быть длинами строк. Я посмотрел алгоритм, но я не мог понять, как его реализовать. Я надеялся получить некоторые подсказки по этому вопросу здесь.

Оптимизация # 4 в разделе «Возможные улучшения».

Часть, которая смутила меня, была та, которая сказала, что нам нужно только вычислить диагональную полосу ширины2k + 1, центрированный по главной диагонали (главная диагональ определяется как координаты (i, i)).

Если бы кто-то мог предложить некоторую помощь / понимание, я был бы очень признателен. При необходимости я могу опубликовать полное описание алгоритма в книге в качестве ответа здесь.