您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

最長公共子序列 (LCS) 算法原理與 Ruby 實作解析

編輯：Java 相關知識

什麼是最長公共子序列 (LCS)？

最長公共子序列問題是經典的動態規劃問題：給定兩個序列，找出它們最長的共同子序列（不要求連續）。例如序列 "ABCBDAB" 和 "BDCABC" 的 LCS 長度為 4，其中一個解為 "BCAB"。LCS 在版本控制、基因序列比對、文本差異比較等領域有廣泛應用。

動態規劃核心邏輯

定義 dp[i][j] 為序列 X 前 i 個字符與序列 Y 前 j 個字符的 LCS 長度。狀態轉移方程：

若 X[i-1] == Y[j-1]：dp[i][j] = dp[i-1][j-1] + 1
否則：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

同時維護一個方向矩陣 b[i][j] 記錄決策來源（0=左上，1=上，2=左），用於回溯構造具體 LCS 序列。

Ruby 參考實作

原文提供的 Ruby 代碼完整演示了 LCS 長度計算與回溯輸出：

# encoding: utf-8
# Longest Common Subsequence (LCS) 實作

chars = ('a'..'e').to_a
x, y = [], []

# 隨機生成兩個測試序列
1.upto(rand(5) + 5) { |i| x << chars[rand(chars.size - 1)] }
1.upto(rand(5) + 5) { |i| y << chars[rand(chars.size - 1)] }

printf("隨機序列: %s 和 %s\n", x, y)

# 初始化 DP 表與方向表
m, n = x.size, y.size
c = Array.new(m + 1) { Array.new(n + 1, 0) }
b = Array.new(m + 1) { Array.new(n + 1, 0) }

# 計算 LCS 長度
def lcs_length(x, y, c, b)
  m, n = x.size, y.size
  (1..m).each do |i|
    (1..n).each do |j|
      if x[i - 1] == y[j - 1]
        c[i][j] = c[i - 1][j - 1] + 1
        b[i][j] = 0  # 來自左上
      elsif c[i - 1][j] >= c[i][j - 1]
        c[i][j] = c[i - 1][j]
        b[i][j] = 1  # 來自上方
      else
        c[i][j] = c[i][j - 1]
        b[i][j] = 2  # 來自左方
      end
    end
  end
end

# 遞迴回溯輸出 LCS
def print_lcs(x, b, i, j)
  return if i == 0 || j == 0
  if b[i][j] == 0
    print_lcs(x, b, i - 1, j - 1)
    printf("%c ", x[i - 1])
  elsif b[i][j] == 1
    print_lcs(x, b, i - 1, j)
  else
    print_lcs(x, b, i, j - 1)
  end
end

lcs_length(x, y, c, b)
print "最長公共子序列: "
print_lcs(x, b, x.size, y.size)
puts

Java 版本對照實作

為方便 Java 開發者理解，以下提供等效的 Java 實現：

import java.util.Arrays;

public class LCS {
    public static String findLCS(char[] x, char[] y) {
        int m = x.length, n = y.length;
        int[][] dp = new int[m + 1][n + 1];
        int[][] dir = new int[m + 1][n + 1]; // 0:↖, 1:↑, 2:←

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x[i - 1] == y[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    dir[i][j] = 0;
                } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j];
                    dir[i][j] = 1;
                } else {
                    dp[i][j] = dp[i][j - 1];
                    dir[i][j] = 2;
                }
            }
        }

        // 回溯構建結果
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (dir[i][j] == 0) {
                lcs.append(x[i - 1]);
                i--; j--;
            } else if (dir[i][j] == 1) {
                i--;
            } else {
                j--;
            }
        }
        return lcs.reverse().toString();
    }

    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCABC";
        System.out.println("LCS: " + findLCS(s1.toCharArray(), s2.toCharArray())); // 輸出: BCAB
    }
}