algorithm - LCS 算法（示例）

Question

有一种动态规划算法可以找到两个序列的最长公共子序列。如何找到两个序列 X 和 Y 的 LCS 算法。（正确性测试）

(a)   X  = ABEDFEESTYH  Y=ABEDFEESTYHABCDF

(b)  X =  BFAAAABBBBBJPRSTY  Y=ABCDEFGHIJKLMNOPRS

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

Answer 1

这是一个在线计算器

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

爪哇

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 2

编辑：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数组中重建最长的子序列（参见 Wikipedia 文章）。

Answer 3

我已经用 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"