LCS算法（示例）

Question

有一個動態規劃算法來查找兩個序列的最長公共子序列。我如何才能找到的兩個序列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/

有一個動態規劃算法找到的最長公共子序列兩個序列（假設這是你的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

這裏是一個在線計算器

http://igm.univ-mlv.fr/~lecroq/seqcomp/node4.html

的Java

public class LCS { 

    public static void main(String[] args) { 
     String x = StdIn.readString(); 
     String y = StdIn.readString(); 
     int M = x.length(); 
     int N = y.length(); 

     // opt[i][j] = length of LCS of x[i..M] and y[j..N] 
     int[][] opt = new int[M+1][N+1]; 

     // compute length of LCS and all subproblems via dynamic programming 
     for (int i = M-1; i >= 0; i--) { 
      for (int j = N-1; j >= 0; j--) { 
       if (x.charAt(i) == y.charAt(j)) 
        opt[i][j] = opt[i+1][j+1] + 1; 
       else 
        opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]); 
      } 
     } 

     // recover LCS itself and print it to standard output 
     int i = 0, j = 0; 
     while(i < M && j < N) { 
      if (x.charAt(i) == y.charAt(j)) { 
       System.out.print(x.charAt(i)); 
       i++; 
       j++; 
      } 
      else if (opt[i+1][j] >= opt[i][j+1]) i++; 
      else         j++; 
     } 
     System.out.println(); 

    } 

} 

Answer 3

我已經寫在Ruby中實現。它是字符串類的擴展：

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"