最長共通部分列 (LCS)｜コードで実践

最長共通部分列 (LCS)

このレッスンで分かること

LCS は「順序を保ったまま、両方に共通する最長の並び」

この遷移を表に埋めていけば、O(len_a * len_b) 時間 / メモリで LCS の長さが求まります

動的計画法基礎編の総仕上げに、最長共通部分列 (Longest Common Subsequence, LCS) に挑戦します

最長共通部分列とは

2 つの文字列の最長共通部分列 (LCS) の長さを 2 次元 DP で求める。文字列系 DP の典型として diff や DNA 解析の土台を学ぶ。

動的計画法基礎編の総仕上げに、最長共通部分列 (Longest Common Subsequence, LCS) に挑戦します。2 つの文字列 a、b が与えられたとき、両方に 同じ順序で現れる文字列 のうち最も長いものの長さを求める問題です。連続している必要はありません。例えば "abcde" と "ace" の LCS は "ace" で長さ 3 です。

この問題は diff コマンド、Git の差分表示、DNA の配列比較 など、現実世界で広く使われています。文字列系の DP では最も基本的かつ重要な問題なので、状態設計と遷移を完全に押さえましょう。

LCS は「順序を保ったまま、両方に共通する最長の並び」。連続でなくてもよい点が肝。

状態と遷移

dp[i][j] を「a の最初の i 文字と b の最初の j 文字における LCS の長さ」と定義します。最終的に欲しいのは dp[len(a)][len(b)] です。

遷移は、最後の 1 文字に注目して場合分けします。

a[i-1] == b[j-1] のとき、その文字を LCS の末尾に加えられるので dp[i][j] = dp[i-1][j-1] + 1
そうでないとき、どちらか片方を捨てて長い方を採用するので dp[i][j] = max(dp[i-1][j], dp[i][j-1])

基底ケースは dp[0][j] = dp[i][0] = 0 (片方が空文字列なら LCS は空)。

diagram (will load when visible)

図のポイント (テキスト併記)

この遷移を表に埋めていけば、O(len_a * len_b) 時間 / メモリで LCS の長さが求まります

この遷移を表に埋めていけば、O(len_a * len_b) 時間 / メモリで LCS の長さが求まります。

「最後の文字を一致させるか、片方を捨てるか」の二択で考えると、文字列 DP は驚くほどシンプルになる。

Python での実装

Python

def longestCommonSubseq(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:
                left = dp[i - 1][j]
                up = dp[i][j - 1]
                dp[i][j] = left if left > up else up
    return dp[n][m]

2 次元 dp を 0 で初期化し、i、j の二重ループで埋めます。a[i-1] == b[j-1] のときだけ斜め上 (dp[i-1][j-1]) から +1、そうでなければ上 (dp[i-1][j]) と左 (dp[i][j-1]) の大きい方を取るだけ。きれいな対称構造です。

JavaScript での実装

JavaScript

function longestCommonSubseq(a, b) {
  const n = a.length;
  const m = b.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const left = dp[i - 1][j];
        const up = dp[i][j - 1];
        dp[i][j] = left > up ? left : up;
      }
    }
  }
  return dp[n][m];
}

JavaScript も同じロジック。Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0)) で 2 次元配列を作るのは、Python の [[0]*(m+1) for _ in range(n+1)] の対応形と覚えると楽です。

よくある間違い

1 つ目は インデックスのずれ。dp[i][j] が「先頭 i 文字」を意味するので、注目する文字は a[i-1]、b[j-1] です。これを混同するとずっと間違った結果が出ます。2 つ目は 文字が一致したのに上下の max も比較する。一致した時点で dp[i-1][j-1] + 1 が最大値であることは証明されているので、追加で max(left, up) と比べる必要はありません (どちらも dp[i-1][j-1] + 1 以下になります)。3 つ目は 空文字列。a = "" や b = "" のとき、結果は 0 ですが、基底ケースで dp[0][*] = dp[*][0] = 0 を確実に初期化していれば自動で正しく動きます。

やってみよう

LCS の長さだけでなく、実際の文字列 を復元してみる。dp 配列を右下から逆順にたどる手順を考える。
同じ DP で「最長共通部分文字列 (連続)」の長さを求めるバリアントを書いてみる。遷移が変わるだけ。
編集距離 (Edit Distance) と LCS の関係を考える。編集距離 = n + m - 2 * LCS (削除・挿入のみのとき)。

LCS は 文字列 DP の入門にして集大成。a[i-1] == b[j-1] の場合分け、(i-1, j-1) から +1 する遷移、上と左の max を取る構造、この 3 点が腑に落ちれば、編集距離や正規表現 DP も同じ要領で書けるようになる。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は 第6章まとめクイズ で、2 つの文字列の最長共通部分列 (LCS) の長さを 2 次元 DP で求めるを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

最長共通部分列の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 最長共通部分列とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

最長共通部分列 (LCS)