最長共通部分列 LCS

🔥 Vibe プロンプト

「DPで'abcde'と'ace'のLCSを発見。DPテーブルと実際のLCS文字列を出力。」

LCSとは？

最長共通部分列（LCS） は、両方の文字列に同じ順序で現れる最長の部分列（連続でなくても良い）を見つける問題です。

| 応用分野 | 用途 | |---------|------| | Git | Diff: ファイル間の共通行を検出 | | バイオインフォマティクス | DNA/RNA配列アラインメント | | 盗作検出 | 文書間の共通テキストを検出 | | スペルチェック | 最も近い辞書単語を発見 |

実装

def lcs(s1, s2):
    """戻り値: (LCSの長さ, LCS文字列)"""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # 一致→斜めから+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # 左か上の最大
    
    # バックトラック
    i, j = m, n
    result = []
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return dp[m][n], ''.join(reversed(result))

# 例
s1, s2 = "abcde", "ace"
length, lcs_str = lcs(s1, s2)
print(f"LCS of '{s1}' and '{s2}'")
print(f"長さ: {length}")
print(f"LCS: '{lcs_str}'")

# Git diffシミュレーション
git_old = "int x = 10;"
git_new = "int y = 20;"
_, common = lcs(git_old, git_new)
print(f"Git diff共通: '{common}'")

DPトレース

"abcde" vs "ace" のテーブル

      ""  a   c   e
""    0   0   0   0
a    0   1   1   1
b    0   1   1   1
c    0   1   2   2
d    0   1   2   2
e    0   1   2   3  ← LCS長=3 ("ace")

まとめ

| 項目 | 詳細 | |------|------| | 状態定義 | dp[i][j] = s1[:i]とs2[:j]のLCS長 | | 漸化式 | 一致時: dp[i-1][j-1]+1 | 不一致時: max(dp[i-1][j], dp[i][j-1]) | | 初期条件 | dp[0][j] = dp[i][0] = 0 | | 時間計算量 | O(m×n) | | 空間計算量 | O(m×n) → O(n)に最適化可能 |

よくある問題と解決策

| 問題 | 原因 | 解決方法 | |------|------|---------| | 期待通りの結果が出ない | パラメータ設定ミス | デフォルト値と境界条件を確認 | | 実行が遅い | アルゴリズムの効率 | より効率的なデータ構造を使用 | | メモリ不足 | データ量過多 | バッチ処理を検討 | | デバッグが困難 | ログ不足 | 詳細なログ出力を追加 |

さらに学ぶには

公式ドキュメントを読む
GitHubのオープンソース例を参照
コミュニティディスカッションに参加
コードを修正して結果の変化を観察