サブシーケンス（部分列）の基礎と応用：判定・出現回数・LCS・LISまで徹底解説

2025年11月21日 最終更新日時 : 2025年11月21日 エバープレイ編集部

サブシーケンスとは

「サブシーケンス（subsequence、部分列）」は、ある列（文字列や配列など）の要素を元の順序を保ったままいくつか取り出して得られる新しい列のことを指します。重要なのは「順序を保つ」ことであり、取り出す要素が元の列で連続している必要はありません。連続して取り出す必要がある場合は「部分文字列（substring）」「サブアレイ（subarray）」「連続部分列」と呼びます。この区別はアルゴリズムや応用の場面でしばしば重要になります。

形式的定義

長さ n の列 S = (s1, s2, …, sn) に対して、インデックスの増加する系列 1 ≤ i1 < i2 < … < ik ≤ n を選ぶと、(si1, si2, …, sik) は S のサブシーケンスである。空列（長さ 0）と元の列自身は常にサブシーケンスに含まれる。

基本的な性質

  • 元の列が長さ n のとき、理論上あり得るサブシーケンスの個数は 2^n（各要素を取る/取らないの二択）である。
  • サブシーケンスは順序を保つが、連続性は不要。連続性を要求したものは部分文字列/サブアレイと呼ぶ。
  • サブシーケンスの概念は文字列だけでなく数列や一般のシーケンス構造に適用できる。

サブシーケンス判定（ある列が別の列のサブシーケンスか）

最も基本的な問題は「文字列 T が文字列 S のサブシーケンスか？」です。効率的なアルゴリズムとしては二つのポインタ（グリーディ）手法があり、O(|S| + |T|) 時間、O(1) 追加空間で判定できます。

簡単な考え方：S 上を先頭から走査し、現在探している T の文字と一致したら T のポインタを一つ進める。T のポインタが最後まで到達したら T は S のサブシーケンス。

i = 0 # S の位置
j = 0 # T の位置
while i < len(S) and j < len(T):
    if S[i] == T[j]:
        j += 1
    i += 1
if j == len(T): return True else False

正当性は単純で、S の走査は常に最も早く見つかる一致を選ぶ（貪欲法が最適である）ことに起因します。

部分列の個数を数える（特定の T の出現回数）

S の中に T が何通りのサブシーケンスとして現れるかを数える問題もよく登場します。これは動的計画法（DP）で解けます。一般的な遷移は次の通りです。

dp[i][j] を S の先頭 i 文字と T の先頭 j 文字について、T[0..j-1] が S[0..i-1] のサブシーケンスとして現れる回数と定義する。遷移：

  • dp[i][0] = 1 （空列は常に1通り）
  • dp[0][j>0] = 0 （S が空なら非空の T は現れない）
  • もし S[i-1] == T[j-1] なら dp[i][j] = dp[i-1][j-1] + dp[i-1][j]（選ぶ/選ばない）
  • そうでなければ dp[i][j] = dp[i-1][j]

計算量は O(|S| * |T|) で、応用として部分列を数える問題（例：S 内に "abc" がいくつ現れるか）に使われます。数が非常に大きくなる場合はモジュロや bignum を用います。

最長共通部分列（LCS）

二つの列 A, B の最長共通部分列（Longest Common Subsequence, LCS）は、両方の列に部分列として現れる最大長の列です。LCS はバージョン管理の差分表示や文字列比較、配列整列問題などで基本的な役割を果たします。

古典的な解法は動的計画法で、dp[i][j] を A の先頭 i 文字と B の先頭 j 文字の LCS の長さと定義し、遷移は：

  • もし A[i-1] == B[j-1] なら dp[i][j] = dp[i-1][j-1] + 1
  • そうでなければ dp[i][j] = max(dp[i-1][j], dp[i][j-1])

時間計算量は O(|A| * |B|)、空間は通常 O(|A| * |B|) ですが、復元を必要としない場合は行ごとの最小化（O(min(|A|,|B|)) 空間）や、解の復元も可能な Hirschberg の分割統治法（空間 O(min(|A|,|B|)) で復元可能）などの工夫があります。

最長増加部分列（LIS） — 別の重要な最長部分列問題

最長増加部分列（Longest Increasing Subsequence）は数列の部分列のうち、値が単調増加するものの最大長を求める問題です。LIS は O(n log n) のアルゴリズムで解けます（パティングソーティングに基づく手法）。基本アイデアは、長さ ℓ の増加部分列の末尾を最小化するように構築すると、二分探索で次の要素の挿入位置を決められる、というものです。

LIS はサブシーケンス問題と関連し、配列の再配置、最小削除数の計算（配列を増加にするための最小削除数は n - LIS 長さ）などに応用されます。

大量クエリや高速判定のための前処理：サブシーケンスオートマトン

多数の T に対して S 上でサブシーケンス判定を高速に行いたい場合、S を前処理して「次に現れる同じ文字の位置」を持つテーブル（次配列、next/automaton）を作る方法が有効です。例えばアルファベットが有限のとき、pos[i][c] を S の位置 i 以降で文字 c が出現する最小位置とすると、各クエリは文字ごとに O(|T|) 時間で判定できます。前処理は O(|S| * Σ)（Σ は文字種）だが、文字種が限定される場合は非常に高速になります。競技プログラミングで頻出のテクニックです。

同様の考えはストリーミングやオンライン判定、複数回のパターン照合で重宝します。

応用例（実務・研究）

  • バージョン管理（diff）: 2 つのファイルの差分は LCS を基に計算されることが多い。
  • バイオインフォマティクス: DNA・タンパク質配列の比較で、ギャップを許容した一致（部分列的な扱い）やモチーフ探索に関連。最長共通部分列は簡略化された類似度指標として利用されることがある。
  • 検索・あいまい検索: 入力文字列が候補のサブシーケンスであるかを調べて曖昧検索を行う（例：補完・略称マッチング）。
  • 競技プログラミング: LCS、LIS、部分列数え上げ、サブシーケンスオートマトンなど多くの典型問題がある。

実装上の注意点

  • Unicode を扱う際は「コードポイント」や「グラフェム（結合文字列）」の扱いに注意する。単純なバイト列や UTF-16 のサロゲートペアでの長さ計算は誤りを招く可能性がある。
  • サブシーケンスの個数は 2^n と急激に増えるため、全列挙は n が小さい場合に限る。列挙よりも動的計画法や組合せ的数え上げが適する。
  • カウントの際はオーバーフロー対策（大きな整数やモジュロ）を行う。
  • アルファベットサイズが大きい（Unicode 全体など）場合、サブシーケンスオートマトンの前処理でメモリが大きくなりがちなのでハッシュやポジションリストを使う最適化を検討する。

参考となるアルゴリズムと計算量まとめ

  • サブシーケンス判定（2 ポインタ）: O(|S| + |T|)
  • 特定 T の出現回数（DP）: O(|S| * |T|)
  • LCS（標準 DP）: O(|A| * |B|) 時間、O(|A| * |B|) 空間（空間最適化あり）
  • LIS（パティングソート法）: O(n log n) 時間
  • サブシーケンスオートマトン（多数クエリ最適化）: 前処理 O(|S| * Σ)・各クエリ O(|T|)

まとめ

サブシーケンスは「順序を保ちつつ任意の要素を選ぶ」概念で、単純ながら多くのアルゴリズム問題や実務用途に登場します。連続性を要求する部分文字列（substring）との違いを意識すること、判定や個数カウント、最長部分列問題にはそれぞれ適したアルゴリズムが存在することがポイントです。大量クエリや大規模データを扱う場合は前処理やデータ構造（次配列、ポジションリスト）による最適化が鍵になります。実装時には文字コードや数のオーバーフローに注意してください。

参考文献

カテゴリー
IT
前の記事
Davy Graham—英国フォーク・リバイバルを牽引したフィンガースタイルの先駆者とDADGADの普及New!!
2025年11月21日
次の記事
Davy Grahamを聴くべき理由と名盤ガイド｜DADGADチューニングと60年代英国フォークの革新を徹底解説New!!
2025年11月21日