algorithm - LCSアルゴリズム（例）

Question

2 つのシーケンスの最長共通サブシーケンスを見つけるための動的計画法アルゴリズムがあります。2 つのシーケンス X と Y の LCS アルゴリズムを見つけるにはどうすればよいですか (正しさのテスト)

(a)   X  = ABEDFEESTYH  Y=ABEDFEESTYHABCDF

(b)  X =  BFAAAABBBBBJPRSTY  Y=ABCDEFGHIJKLMNOPRS

(c)  X = ϕ (Empty Sequence), Y = BABADCAB

Answer 1

編集:C++実装: http://comeoncodeon.wordpress.com/2009/08/07/longest-common-subsequence-lcs/

2 つのシーケンスの最長共通サブシーケンスを見つけるための動的プログラミング アルゴリズムがあります (LCS が意味するものと仮定して): http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

これが再発です（ウィキペディアから）：

および擬似コード（これもウィキペディアから）：

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else:
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

その後、C配列から最長のサブシーケンスを再構築することができます (ウィキペディアの記事を参照してください)。

Answer 2

Rubyで実装を書きました。これは String Class の拡張です:

class String

def lcs_with(str)
    unless str.is_a? String
        raise ArgumentError,"Need a string"
    end

    n = self.length + 1
    m = str.length + 1

    matrix = Array.new(n, nil)
    matrix.each_index  do |i|
        matrix[i] = Array.new(m, 0)
    end

    1.upto(n - 1) do |i|
        1.upto(m - 1) do |j|
            if self[i] == str[j]
                matrix[i][j] = matrix[i - 1][j - 1] + 1
            else
                matrix[i][j] = [matrix[i][j - 1], matrix[i - 1][j]].max
            end
        end
    end
    matrix[self.length][str.length]
end 

end

puts "ABEDFEESTYH".lcs_with "ABEDFEESTYHABCDF"