最長共通部分列
2つの文字列に対するLCSの漸化式を定義して2Dテーブルを埋め、テーブルを逆にたどって実際の部分列を復元します。
「最長共通部分列」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
部分列とは
文字列の部分列とは、残す文字の順序を変えずに、一部またはすべての文字を削除して作られるものです。たとえば「ACE」は「ABCDE」の部分列ですが、「AEC」は部分列ではありません（順序が変わっているためです）。2つの文字列に共通する最長の部分列を最長共通部分列（LCS）と呼びます。「ABCBDAB」と「BDCABA」に共通するLCSは、「BCBA」または「BDAB」で、長さは4です。
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueLCSの漸化式の導出
dp[i][j] を text1[:i] と text2[:j] のLCSの長さと定義します。文字が一致する場合（text1[i-1] == text2[j-1]）、LCSを1文字分伸ばせるため、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の長さは0です）。
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2LCSテーブルの追跡
text1='ABCD'、text2='ACBD' の場合を考えます。まず、すべてを0で初期化します。文字が一致する箇所（A-A、C-C、正しい位置にあるB-B、D-D）では、dp[i][j] = dp[i-1][j-1] + 1 となります。それ以外では、左と上の近傍の最大値を取ります。埋めたテーブルを順に確認すると、斜め方向の移動が一致した文字に対応していることが分かります。最終値 dp[4][4] がLCSの長さを表します。
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')実際のLCSの復元
実際のLCS文字列を復元するには、dp[m][n]からDPテーブルをバックトラックします。text1[i-1] == text2[j-1]の場合、この文字はLCSに含まれるため記録し、(i-1, j-1)へ斜めに移動します。dp[i-1][j] > dp[i][j-1]の場合は上へ、それ以外は左へ移動します。バックトラックでは文字を逆順に集めるため、最後に集めた文字を反転します。この復元はO(m+n)時間で実行できます。
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABO(n)への空間最適化
LCSテーブルで必要なのは、現在の行と直前の行だけです。サイズがn+1の1次元配列と、上書きされる前のdp[i-1][j-1]の値を保持する変数diagonalを使用できます。各行では左から右へ反復します。各セルの処理後、更新されたdp[j]には現在の行の値が格納され、上書きする前の値をdiagonalに保存します。
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4LCSと編集距離の関係
LCSは編集距離（レーベンシュタイン距離）と密接に関係しています。LCSがわかっていれば、挿入と削除だけを使った最小編集距離をedit_dist = m + n - 2 * LCS(s1, s2)で計算できます。s1でLCSに含まれない各文字には削除が必要で、s2でLCSに含まれない各文字には挿入が必要です。ここでは挿入と削除だけを許可するため置換は数えませんが、この式は関連する問題で役立ちます。
def lcs_length(s1, s2):
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
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 52つの文字列に対する削除操作
2つの文字列に対する削除操作（LeetCode 583）では、2つの文字列を等しくするために必要な削除回数の最小値を求めます。残す文字は共通部分列でなければならないため、LCSを最大化し、それ以外をすべて削除します。答えはm + n - 2 * LCS(s1, s2)です。これは前述の挿入と削除による編集距離と同値です。問題をLCSの観点で捉えることは、強力な帰着テクニックです。
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4最長共通部分文字列
LCS（部分列）と最長共通部分文字列を混同しないでください。部分文字列は連続している必要があるため、文字が一致しない場合は近傍の最大値を取るのではなく、カウントを0にリセットします。漸化式は次のように変わります。一致する場合はdp[i][j] = dp[i-1][j-1] + 1、それ以外の場合はdp[i][j] = 0です。すべてのセルで得られた最大値を記録します。
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
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
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)系列比較のためのLCS
LCSは、ファイルを比較する差分ツール（Unixのdiffなど）で広く使用されています。2つのファイル間の編集スクリプトはLCSから導出されます。LCSに含まれる行は変更されず、ファイル1にのみ存在する行は削除され、ファイル2にのみ存在する行は挿入されます。LCSを理解すると、バージョン管理システムが変更を追跡する方法や、マージの競合が発生する理由を理解しやすくなります。
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)最短共通スーパーシーケンス
最短共通スーパーシーケンス（LeetCode 1092）では、s1とs2の両方を部分列として含む最短の文字列を求めます。スーパーシーケンスでは、LCSの各文字は1回だけ現れます。LCSに含まれない両方の文字列の文字はすべて含める必要があります。長さはm + n - LCS(s1, s2)です。復元するには、同じLCSのバックトラックを使用し、一致しない位置では両方の文字列の文字を含めます。
def shortest_common_supersequence(s1, s2):
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
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Reconstruct
result, i, j = [], m, n
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]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5LCSの計算量と面接のヒント
標準的なLCSアルゴリズムはO(m×n)時間、O(m×n)空間で実行され、ローリング配列のテクニックによってO(min(m,n))空間まで削減できます。面接での重要なヒントは次のとおりです。(1) コーディング前に、DPの状態が何を表すのかを明確に定義します。(2) 一致する場合と一致しない場合を明確に分けて処理します。(3) 系列の復元を求められたら、実装前にバックトラックの方法を説明します。(4) 関連する1次元問題として、忍耐ソートを使ってO(n log n)で解ける最長増加部分列（LIS）にも言及します。
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)クイックチェック
このレッスンのData Structures & Algorithms — Coding Interview Prepに関する理解度を確認します。
レッスンのまとめ
このレッスンでは、LCSでは、マッチ時に dp[i][j] = dp[i-1][j-1]+1 を使用し、それ以外では max(dp[i-1][j], dp[i][j-1]) を使用すること、実際の系列は、一致時には斜めに、相違時にはより大きい隣接セルの方向へバックトラックして復元すること、そしてLCSが編集距離、削除操作、最短共通スーパーシーケンス、差分ツールの基盤になっていることを学びました。次は、LCSの枠組みに置換を加えた編集距離（レーベンシュタイン距離）の漸化式を導出します。
よくある質問
「最長共通部分列」レッスンは無料ですか？
はい。「最長共通部分列」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「最長共通部分列」で何を学びますか？
2つの文字列に対するLCSの漸化式を定義して2Dテーブルを埋め、テーブルを逆にたどって実際の部分列を復元します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「最長共通部分列」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。