アルゴリズム：最長共通部分列問題

問題の背景#

与えられた 2 つの文字列 A と B の最長共通部分列を見つけます。

部分列：連続していなくてもよいが、元の順序を保持する
共通部分列：A と B の両方の部分列である

例：

A = "ABCBDAB"
B = "BDCAB"

LCS = "BDAB" または "BCAB"（どちらも長さは4）

応用#

ファイル / コードの差分比較（例えば diff ツール）
遺伝子配列の比較（DNA / タンパク質）
スペルチェック、バージョン管理のマージ
編集距離、意味的類似性の計算

動的計画法による解法#

考え方： $dp[i][j]$ を $A[0..i-1]$ と $B[0..j-1]$ の最長共通部分列の長さを表すように定義します。

擬似コード（状態遷移方程式を含む）：

def LCS_length(A, B):
    n, m = len(A), len(B)
    dp = [[0] * (m+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, m+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[n][m]

時間計算量： $O(m\times n)$
空間計算量： $O(m\times n)$

戻り道と列の復元#

  # ...

  # 戻り道を復元
  i, j = n, m
  lcs = []
  while i > 0 and j > 0:
      if A[i-1] == B[j-1]:
          lcs.append(A[i-1])
          i -= 1
          j -= 1
      elif dp[i-1][j] >= dp[i][j-1]:
          i -= 1
      else:
          j -= 1

  return ''.join(reversed(lcs))

ローリングアレイによる空間計算量の最適化#

2 次元 DP テーブルにおいて、ある行の値が「前の行」のみ依存している場合、全体の 2 次元テーブルを保持する必要はありません —— 現在の行と前の行だけを保存すればよいのです。

元の状態遷移：

if A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

各 dp [i][j] は i-1 行のデータのみに依存しているため、ローリングアレイで空間を最適化できます。

ローリングアレイの実装方法
2 行だけを保持します。

prev = [0] * (m + 1)  # 前の行
curr = [0] * (m + 1)  # 現在の行

各行 i を処理した後、prev と curr を交換します。

def LCS_length(A, B):
    n, m = len(A), len(B)
    prev = [0] * (m + 1)
    curr = [0] * (m + 1)

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, prev  # 2行を交換

    return prev[m]  # 最終結果は prev にある（最後のラウンドで交換されたため）

時間計算量は依然として $O(m\times n)$
空間計算量は $O(\min\{m, n\})$ に減少します。

ただし注意：ローリングアレイに基づいて LCS のパスを復元することはできません。なぜなら、パス情報は空間圧縮の中で失われてしまったからです。