最長共通部分列

2025年10月20日

最長共通部分列

英語表記: Longest Common Subsequence

概要

最長共通部分列（LCS）とは、二つの異なる列（文字列や数列）に共通して含まれる部分列のうち、最も長いものを求める問題です。ここでいう「部分列」は、元の列の要素の順序を変えずに、一部の要素を取り出して作られる列のことを指します。例えば、「ABCDE」と「AXBYCZD」の共通部分列は「ABD」や「ACD」などが考えられますが、最も長いものは「ACD」（長さ3）となります。

このLCS問題は、「アルゴリズムと計算量」の分野において、計算効率が非常に高い「動的計画法」（Dynamic Programming, DP）を適用する際の最も有名な「典型問題」の一つとして位置づけられています。複雑な問題を小さな問題に分割し、その結果を再利用することで、飛躍的に処理速度を向上させることができる、動的計画法の真髄が詰まったテーマだと言えるでしょう。

詳細解説

LCSが動的計画法の典型問題である理由

LCS問題を単純に解こうとすると、一方の列のすべての部分列と、もう一方の列のすべての部分列を比較するという途方もない作業が必要になります。これは指数関数的な計算量となり、現実的な時間で解くことは不可能です。

しかし、LCS問題は動的計画法の適用に必要な二つの重要な特性を持っています。

最適性の構造（Optimal Substructure）: 問題の最適解が、部分問題の最適解から構成されています。二つの列のLCSを求める際、それぞれの末尾の文字を比較することで、より短い列のLCSを求める問題に還元できるのです。
重複する部分問題（Overlapping Subproblems）: 同じ部分問題が何度も繰り返し現れます。動的計画法では、この重複する部分問題の解を一度計算したら記憶（メモ化、またはDPテーブルの利用）しておき、再利用することで、無駄な計算を徹底的に排除します。

DPテーブルを用いた動作原理

LCSを動的計画法で解く場合、二つの文字列の長さをそれぞれ $M$ と $N$ とすると、$M \times N$ の大きさを持つ二次元配列（DPテーブル）を作成します。このテーブルの各セル $DP[i][j]$ には、「最初の文字列の $i$ 文字目まで」と「二番目の文字列の $j$ 文字目まで」を使った場合の最長共通部分列の長さが記録されます。

このテーブルを埋める際の漸化式（更新ルール）こそが、LCSアルゴリズムの核心であり、私たちが動的計画法を学ぶ上で最も感動するポイントです。

漸化式（基本ロジック）:

文字が一致する場合: もし $i$ 文字目と $j$ 文字目が同じであれば、共通部分列の長さは一つ伸びたことになります。したがって、斜め左上のセル $DP[i-1][j-1]$ の値に 1 を加算します。
$$DP[i][j] = DP[i-1][j-1] + 1$$
文字が一致しない場合: 共通部分列の長さは伸びません。この場合、私たちは二つの選択肢のうち、より長い共通部分列を与えてくれる方を選びます。つまり、「$i$ 文字目を無視して $j$ 文字目までで考える」($DP[i-1][j]$) か、「$j$ 文字目を無視して $i$ 文字目までで考える」($DP[i][j-1]$) のうち、大きい方を選びます。
$$DP[i][j] = \max(DP[i-1][j], DP[i][j-1])$$

このシンプルなルールに従ってテーブルを左上から順に埋めていくだけで、最終的に右下のセル $DP[M][N]$ には、二つの文字列全体の最長共通部分列の長さが出現します。計算量は $O(MN)$ となり、これは指数関数的な計算量に比べて圧倒的に効率的です。アルゴリズムと計算量を考える上で、この効率性の改善こそが動的計画法の最大の貢献なのです。

具体例・活用シーン

LCSは、一見すると学術的な問題に見えますが、実は私たちの身の回りにある多くのシステムの基礎を支えています。

活用シーン

遺伝子配列解析（バイオインフォマティクス）: 二つのDNA配列やタンパク質配列の類似性を測るためにLCSが使用されます。共通部分が長いほど、それらの生物学的機能や進化上の近さが示唆されます。
ファイル比較ツール（Diffツール）: プログラミングにおいて、二つのバージョンのソースコードやテキストファイルを比較し、どの行が追加、削除、変更されたかを検出する際に、LCSの考え方が応用されています。共通部分列が長いほど、変更されていないコアな部分が多いと判断できます。
スペルチェック・校正支援: 入力された単語と辞書内の単語のLCSを計算することで、どれだけ似ているかを判断し、最も近い単語を候補として提示する際の基礎技術となります。

アナロジー：二人の編集者と原稿のコア

LCSの動作を理解するための具体例として、「二人の編集者による原稿の校正」を考えてみましょう。

ある小説家が書いたオリジナルの原稿（列A）を、編集者Pと編集者Qの二人に渡しました。PはPなりの修正を加え（列P）、QはQなりの修正を加えました（列Q）。

ここで私たちが知りたいのは、「PとQ、両方が変更しなかった、あるいは偶然にも同じ順序で残した、原稿の最も核となる構造」です。

列A（オリジナル）: 「あの素晴らしい本を、私は昨日、図書館で読み終えた。」
列P（Pの修正）: 「あの、私は昨日、図書館で読み終えた。」（「素晴らしい本を」を削除）
列Q（Qの修正）: 「あの素晴らしい本を、昨日、読み終えた。」（「私は」と「図書館で」を削除）

このPとQの文章を比較する際、LCSアルゴリズムが適用されます。

LCSによって抽出されるのは、「あの」, 「昨日」, 「読み終えた」 のような共通の単語の並びです。この共通部分列こそが、二人の編集者が独立して作業を行ったにもかかわらず、本質的に残された「原稿のコア」を示しています。

動的計画法は、このコアを見つけ出す作業を、単語一つ一つを比較するたびに「そこまでの最長のコアは何か？」と過去の情報を参照しながら積み上げていく、非常に計画的で無駄のない方法なのです。これは、まるで熟練の職人が、小さな部品を一つずつ組み上げ、最終的に巨大で完璧な構造物を作り上げる様子に似ています。過去の作業結果を常に記憶し、決して同じ作業を二度繰り返さない、という知恵の結晶が動的計画法であり、LCSはその最も美しい実践例だと言えるでしょう。

資格試験向けチェックポイント

LCSは、特に応用情報技術者試験や基本情報技術者試験において、動的計画法の理解度を測るための重要なテーマとして頻出します。ITパスポート試験では直接的な計算問題は出ませんが、概念理解が問われる可能性があります。

動的計画法の適用条件: LCSがなぜ動的計画法で解かれるのか（最適性の構造と重複する部分問題）を理解しておくことが必須です。問題文で「最適解を求める」「重複する計算を避ける」といったキーワードがあれば、動的計画法を疑ってください。
計算量: LCSをDPで解いた場合の計算量は、二つの列の長さを $M$ と $N$ とした場合、$O(MN)$ であることを覚えておきましょう。これは、すべてのセルを一度ずつ埋める必要があるためです。この効率性の改善こそが、アルゴリズムの分野でLCSが重要視される理由です。
部分列と部分文字列の区別: 「部分列 (Subsequence)」は元の順序を保てば要素をスキップしても良いのに対し、「部分文字列 (Substring)」は連続している必要があります。LCSは「部分列」を求める問題であり、この違いを混同しないように注意が必要です。
DPテーブルの読解: 漸化式自体を記述させる問題は稀ですが、与えられたDPテーブルの一部が空欄になっており、その空欄を埋める問題や、特定のセルの値がなぜそうなるのかを説明させるパターンが出題されます。特に「一致しない場合の $\max$ を取る」ロジックを理解しているかどうかが重要になります。
応用問題への拡張: LCSの概念は、最小編集距離（Edit Distance）や、最長増加部分列（LIS）など、他の動的計画法の典型問題と密接に関連しています。LCSの理解は、これらの応用問題への足がかりとなります。