eu recentementepostou uma pergunta sobre como otimizar o algoritmo para calcular a distância de Levenshtein, e as respostas me levam ao artigo da Wikipedia sobreDistância Levenshtein.

O artigo mencionou que, se houver um limitek na distância máxima, um resultado possível pode ser da consulta em questão, e o tempo de execução pode ser reduzido deO (mn) paraO (kn), m en sendo os comprimentos das cordas. Procurei o algoritmo, mas não conseguia descobrir como implementá-lo. Eu esperava obter algumas pistas sobre isso aqui.

A otimização é a número 4 em "Melhorias possíveis".

A parte que me confundiu foi a que disse que só precisamos calcular uma faixa diagonal de largura2k + 1, centralizado na diagonal principal (a diagonal principal é definida como coordenadas (i, i)).

Se alguém pudesse oferecer alguma ajuda / insight, eu realmente apreciaria. Se necessário, posso postar a descrição completa do algoritmo no livro como resposta aqui.