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

Ruby 實現最長公共子序列 (LCS) 動態規劃演算法

編輯：更多程式設計知識

最長公共子序列問題：給定兩序列，找出最長的子序列（不要求連續）同時出現在兩者中。本文提供標準動態規劃 Ruby 實作，包含長度矩陣建構、方向追蹤矩陣、遞迴回溯列印 LCS 內容。

完整程式碼


# encoding: utf-8

# 隨機生成測試序列
chars = ('a'..'e').to_a
x, y = [], []
(rand(5)+5).times { x << chars[rand(chars.size)] }
(rand(5)+5).times { y << chars[rand(chars.size)] }
printf("The random character arrays are: %s and %s\n", x.inspect, y.inspect)

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=斜上, 1=上, 2=左

# DP 填表
(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  # 斜上 (匹配)
    else
      if 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)
    print "#{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

print "The Longest-Common-Subsequence is: "
print_lcs(x, b, m, n)
puts

執行範例


The random character arrays are: ["b", "a", "c", "a", "a", "b", "d"] and ["a", "c", "a", "c", "a", "a", "b"]
The Longest-Common-Subsequence is: a c a a b

演算法解析

狀態定義

c[i][j]：X[1..i] 與 Y[1..j] 的 LCS 長度
b[i][j]：最優解來源方向
- 0：X[i]==Y[j]，來自 c[i-1][j-1] (斜上)
- 1：來自 c[i-1][j] (上)
- 2：來自 c[i][j-1] (左)

轉移方程

if X[i] == Y[j]:
    c[i][j] = c[i-1][j-1] + 1
    b[i][j] = 0
else:
    c[i][j] = max(c[i-1][j], c[i][j-1])
    b[i][j] = (c[i-1][j] >= c[i][j-1]) ? 1 : 2

回溯邏輯

從 c[m][n] 起始，依 b 方向遞迴
方向 0：輸出字元，移至 (i-1, j-1)
方向 1：移至 (i-1, j)
方向 2：移至 (i, j-1)

複雜度

時間：O(mn)
空間：O(mn) — 可優化至 O(min(m,n)) 僅保留長度，但無法回溯列印 LCS 內容

變體與應用

變體	修改點	應用
最長公共子串	要求連續，不匹配時歸零	相似度檢測、病毒特徵碼
編輯距離	允許替換操作	拼字檢查、DNA 比對
最長遞增子序列 (LIS)	單序列，轉化為 LCS	版本號排序、橋樑建設
多序列 LCS	擴充至 k 維 DP	多基因組比對