Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Levenshtein substring minimal distance, javascript implementation
LevenshteinSubminimal(String A, String B) -> {k: Integer, t: String}
A, es la cadena que introduce el usuario
B, es la cadena candidata a ser alternativa del usuario
k, es la mínima Levenshtein de A sobre todas las subcadenas de B
t, es la cadena con menor distancia Levenshtein
function LevenshteinSubminimal(A, B) {
var a = A.length;
var b = B.length;
// siempre comparamos A con las subcadenas de B
var f = function(s){return Levenshtein(A, s)};
// si A es mayor que B no comparamos subcadenas
if(a >= b)
return {k: f(B), t: B}
// peor caso y cotas
var m = {k: b+2, t: null}, c1 = a-1, c2 = a+1;
for(var p = 0; p < b - c1; p++)
for(var l = c1, c3 = Math.min(c2, b - p); l <= c3; l++) {
var t = B.substr(p, l), k = f(t);
// mejor caso
if(m.k >= k)
m = {k: k, t: t};
return m;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.