Existe-t-il un meilleur moyen de comparer les chaînes dans un délai raisonnable?

Question

J'ai cette fonction Ruby qui me dit si deux chaînes sont "presque" égales, c'est-à-dire si tous les caractères de la chaîne sont identiques et ordonnés de la même manière sauf un. Ainsi, par exemple, ceux-ci sont égaux

equal 
eual 

mais ceux-ci ne sont pas

eal 
equal 

(deux caractères sont manquants dans ce qui précède). Donc, avec l'aide, je suis venu avec cette

(lcs(a,b) == shortest && longest.length - shortest.length == 1) 

dans lequel las est définie par

def lcs(xstr, ystr) 
    return "" if xstr.empty? || ystr.empty? 

    x, xs, y, ys = xstr[0..0], xstr[1..-1], ystr[0..0], ystr[1..-1] 
    if x == y 
     x + lcs(xs, ys) 
    else 
     [lcs(xstr, ys), lcs(xs, ystr)].max_by {|x| x.size} 
    end 
    end 

mais ma fonction prend un temps extraordinairement long. Notez mon indice de référence ci-dessous

2.4.0 :011 > timing = Benchmark.measure { StringHelper.lcs("navesxkolsky|1227000", "navsxkolsky|1227000") } 
=> #<Benchmark::Tms:0x007fa1753830d8 @label="", @real=21.341279999993276, @cstime=0.0, @cutime=0.0, @stime=0.030000000000000027, @utime=21.28, @total=21.310000000000002> 

Y at-il quelque chose que je manque ici qui peut obtenir mon temps de comparaison jusqu'à comme un seconde au lieu de 21?

Answer 1

Essayez ceci. L'idée principale est que si la méthode doit renvoyer false, elle le fera dès que cela sera connu, même si un code rudongant est requis. (La méthode ci-dessous fonctionne toujours si la ligne return false if (sz1-sz2).abs > 1 est retirée.)

def equal_but_one?(str1, str2) 
    sz1 = str1.size 
    sz2 = str2.size 
    return false if (sz1-sz2).abs > 1 
    i = [sz1, sz2].max.times.find { |i| str1[i] != str2[i] } 
    return false if i.nil? 
    case sz1 <=> sz2 
    when 0 
    str1[i+1..-1] == str2[i+1..-1] 
    when -1 
    str2[i+1..-1] == str1[i..-1] 
    when 1 
    str1[i+1..-1] == str2[i..-1] 
    end 
end 

equal_but_one?('cat', 'cut')  #=> true 
equal_but_one?('bates', 'bats') #=> true 
equal_but_one?('buss', 'bus') #=> true 
equal_but_one?('cat', 'cat')  #=> false 
equal_but_one?('pig', 'pigs') #=> true 
equal_but_one?('pig', 'pegs') #=> false 
equal_but_one?('', '')   #=> false 
equal_but_one?('', 'a')   #=> true 

require 'benchmark' 

Benchmark.measure { equal_but_one?("navesxkolsky|1227000", "navsxkolsky|1227000") }.real 
    #=> 1.6000005416572094e-05