部分列と最長共通部分列（subsequence / longest common subsequence）
元の並び順を保ったまま、いくつか取り出した列が部分列。2つの列の両方に現れる部分列のうち最も長いものが最長共通部分列。
もう少し詳しい説明
部分列とは
部分列は、元の列から要素をいくつか取り出した列です。取り出した要素の順番は元のままにします。
「ABCD」の部分列の例：
| 部分列 | 元のどこから取ったか |
|---|---|
| A | 1番目 |
| AC | 1番目と3番目 |
| ABD | 1番目、2番目、4番目 |
| ABCD | 全部 |
連続していなくてもかまいません。 ここが似た言葉との分かれ目です。
| 語 | 連続しているか |
|---|---|
| 部分列（subsequence） | 連続していなくてよい |
| 部分文字列（substring） | 連続していなければならない |
「ABCD」に対して、「AC」は部分列ですが、部分文字列ではありません。
順番を入れ替えたものは部分列ではありません。 「DA」は、元の並びでAのほうが先にあるので、部分列に入りません。
最長共通部分列
2つの列の両方に現れる部分列のうち、最も長いものです。英語の頭文字からLCSと呼ばれます。
例として「ABCBDAB」と「BDCABA」で考えます。
| 両方に現れる部分列 | 長さ |
|---|---|
| BD | 2 |
| BCA | 3 |
| BCBA | 4 |
この場合の最長共通部分列は「BCBA」で、長さは4です。
| 列 | 取り出した位置（1から数える） |
|---|---|
| ABCBDAB | 2番目B、3番目C、4番目B、6番目A |
| BDCABA | 1番目B、3番目C、4番目A… |
最長共通部分列は1つに決まらないことがあります。 同じ長さのものが複数あるときです。長さのほうは1つに決まります。
何に使うのか
- 2つの文書の違いを出す（変更のない行が共通部分列にあたる）
- 遺伝子の配列を比べる
- 入力の誤りを直す候補を出す
同じところを最大限に取り、残りを違いとして扱うという使い方です。
全部試すと間に合わない
長さnの列の部分列は、各要素を取る・取らないで決まるので 2のn乗通りあります。
| nの値 | 部分列の数 |
|---|---|
| 10 | 1,024 |
| 20 | 1,048,576 |
| 40 | 約1兆 |
両方の列で全部作って突き合わせる方法は、列が長くなると終わりません。 そこで表を使って求める動的計画法に進みます。
試験ではこう出る
応用情報の午後（プログラミング）では、最長共通部分列の長さを求める処理が題材になります。擬似言語で書かれた処理を読み、表の値を追う形です。
部分列と部分文字列の区別は、設問の前提として置かれます。ここを取り違えると、表の意味が合わなくなります。
関連する用語
ミニクイズ
文字列「ABCD」の部分列として**正しくない**ものはどれか。
正解は 3番：DA
部分列は、元の列から文字をいくつか取り出した列で、取り出した文字の順番は元の並びのままにします。ABCDではAがDより先にあるので、DAという順にはなりません。ACはAのあとにC、ABDはAのあとにB、そのあとにD、BDはBのあとにDで、いずれも元の並び順を保っています。連続している必要はない点が、部分文字列との違いです。
この分野をまとめて解く → アルゴリズムとプログラミングのミニテスト（全44問）
最終更新：2026-11-09