gistfile1.builder

def dameraulevenshtein(seq1, seq2)
        len1 = seq1.length
        len2 = seq2.length
        oneago = nil
        row = (1..len2).to_a << 0
        len1.times do |i|
                twoago, oneago, row = oneago, row, Array.new(len2) {0} << (i + 1)
                len2.times do |j|
                        cost = seq1[i] == seq2[j] ? 0 : 1
                        delcost = oneago[j] + 1
                        addcost = row[j - 1] + 1
                        subcost = oneago[j - 1] + cost
                        row[j] = [delcost, addcost, subcost].min
                        if i > 0 and j > 0 and seq1[i] == seq2[j-1] and
                                seq1[i-1] == seq2[j]
                                row[j] = [row[j], twoago[j - 2] + cost].min
                        end
                end
        end

        return row[len2 - 1]
end