Longest Common Subsequence
2つの文字列 text1 と text2 が与えられます。文字列の部分列とは、文字の一部を元の順序のまま残し、残りを削除したものです。残す文字は隣り合っている必要はありません。両方の文字列の部分列である最長の文字列の長さを返してください。共通する文字がない場合は 0 を返してください。
関数
- text1string
- 最初の文字列
- text2string
- 2番目の文字列
- 戻り値integer
- 最長共通部分列の長さ
制約
1 ≤ text1.length ≤ 10001 ≤ text2.length ≤ 1000- 両方の文字列には、小文字の英字のみが含まれています。
例
- 入力
- text1 = "stone"text2 = "longest"
- 出力
- 3
- 説明
- o、n、eは両方の単語にこの順序で現れるため、共通するのは長さ3の
oneです。文字sとtはlongestでは最後に現れますが、stoneでは最初に現れるため、これらを使っても最大でstまでです。
- 入力
- text1 = "pear"text2 = "reap"
- 出力
- 2
- 説明
eaは両方の単語に含まれています。2つの単語では、pとrはeaの反対側にあるため、どちらもそれに結合できません。したがって、答えは2です。
- 入力
- text1 = "cat"text2 = "dog"
- 出力
- 0
- 説明
- この2つの単語には共通する文字がないため、共通部分列は空のものだけで、その長さは0です。
発展問題
最長共通部分列の長さとともに、そのうちの1つ自体を返すことはできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各文字列の最後の文字を見てください。2つの文字が同じ場合、答えについて何が言えますか？異なる場合はどうですか？
文字が一致する場合はそれらを組み合わせ、残りは両方の文字列からその文字を取り除いた同じ問題です。一致しない場合は、少なくとも一方は使われないため、それぞれを取り除いて試し、よりよい答えを選びます。
同じ接頭辞の長さのペアが何度も出てきます。接頭辞の長さの各ペア
(i, j)に対する答えを表に保存し、答えが 0 となる空の接頭辞から始めて、行ごとに埋めていき、最後のセルから答えを読み取ります。
解説
貪欲なマッチングではうまくいきません。cab の c を abc の最後の c と対応させると、a と b に対応するものが残りません。これを飛ばせば ab が見つかります。2つの接頭辞に対する答えは、より短い接頭辞に対する答えに依存するため、(n+1) × (m+1) の表を使えば、すべての組み合わせを一度ずつ解けます。各行で参照するのは直上の行だけなので、2行あれば十分です。
再帰を使って最初の文字を比較する
正しいが、最大のテストでは終わらない
考え方
lcs(i, j)を、接尾辞text1[i:]とtext2[j:]に対する答えとします。先頭の文字が等しければ、それらを組にします。この組を飛ばす最長共通部分列があっても、その最初の組をこちらの組に置き換えても長さは短くなりません。したがって答えは1 + lcs(i+1, j+1)です。
文字が異なる場合、両方を使うことはできません。対応する文字の組が交差してしまうためです。したがって、どちらか一方を除外できます。max(lcs(i+1, j), lcs(i, j+1))です。空の接尾辞に対する答えは0です。
文字が一致しないたびに、呼び出しが2つ始まります。共通の文字を持たない20文字の文字列2つだけでも、呼び出し回数は約2.8 × 10^11回になります。しかし、異なる組(i, j)は(n+1) × (m+1)個しかないため、ほとんどの呼び出しは以前の呼び出しの繰り返しです。
アルゴリズム
iとjから始まる接尾辞について、lcs(i, j)を記述します。iまたはjがそれぞれの文字列の末尾を過ぎている場合は、0 を返します。text1[i] == text2[j]の場合は、1 + lcs(i+1, j+1)を返します。- それ以外の場合は、
max(lcs(i+1, j), lcs(i, j+1))を返します。 - 答えは
lcs(0, 0)です。
def longestCommonSubsequence(text1, text2):
def lcs(i, j):
# The longest common subsequence of text1[i:] and text2[j:]
if i == len(text1) or j == len(text2):
return 0
if text1[i] == text2[j]:
return 1 + lcs(i + 1, j + 1)
return max(lcs(i + 1, j), lcs(i, j + 1))
return lcs(0, 0)接頭辞の表を埋めてください
考え方
dp[i][j]を、text1の最初のi文字とtext2の最初のj文字に対する答えとします。インデックス0は空の接頭辞を意味するため、0行目と0列目は0です。2つの接頭辞の最後の文字、text1[i-1]とtext2[j-1]を比較します。同じ文字なら対応させてdp[i-1][j-1] + 1、異なる文字ならどちらか一方を除いてmax(dp[i-1][j], dp[i][j-1])です。これは末尾から読む再帰です。
各セルは上、左、左斜め上のセルを参照するため、行ごとに左から右へ埋めれば、参照先の値は常に計算済みです。pearとreapの場合、peaの行は[0, 0, 1, 2, 2]です。reaに対応するセルの値が2なのは、a同士が一致し、peとreに対応するセルの値に1を加えるためです。
1000文字の文字列2つなら、定数時間のステップが約10^6回かかります。
アルゴリズム
(n+1) × (m+1)個のゼロでテーブルdpを作成します。iを 1 からnまで、jを 1 からmまで動かし、text1[i-1]とtext2[j-1]を比較します。- 一致した場合は、
dp[i][j] = dp[i-1][j-1] + 1を設定します。 - それ以外の場合は、
dp[i][j] = max(dp[i-1][j], dp[i][j-1])を設定します。 dp[n][m]を返します。
def longestCommonSubsequence(text1, text2):
n, m = len(text1), len(text2)
# dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
# Row 0 and column 0 stay 0: an empty prefix has nothing in common.
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 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])
return dp[n][m]2行だけを残す
考え方
ある行の処理が終わると、その上の行が再び読み込まれることはありません。完了した行にはprev、値を埋めている行にはcurを使い、各行の処理後に入れ替えます。漸化式と順序はそのままです。
答えはどちらの文字列が先かには依存しないので、行は短い方に沿って処理します。すると各行に保持する数値はmin(n, m) + 1個です。最大の入力でも、100万個のセルの代わりに1001個で済み、ステップ数は同じ10^6です。
アルゴリズム
text2がtext1より長い場合は、入れ替えます。prevとcurを作成します。それぞれの要素数はm + 1で、すべて0にします。ここでmは短い方の長さです。text1の各文字について、上の行にあたるprevを参照し、表と同じルールでcur[1..m]を埋めます。prevとcurを入れ替えます。prev[m]を返します。
def longestCommonSubsequence(text1, text2):
if len(text2) > len(text1):
text1, text2 = text2, text1 # keep the rows as short as the shorter string
m = len(text2)
# prev[j]: the answer for the previous prefix of text1 and text2[:j]
prev = [0] * (m + 1)
for ch in text1:
cur = [0] * (m + 1)
for j in range(1, m + 1):
if ch == text2[j - 1]:
cur[j] = prev[j - 1] + 1
else:
cur[j] = max(prev[j], cur[j - 1])
prev = cur
return prev[m]
落とし穴と境界ケース
- 表のインデックスと文字列のインデックスを混同する。セル
dp[i][j]では、行 0 が空の接頭辞を表すため、text1[i-1]とtext2[j-1]を比較する。 - 一致したときに、
dp[i-1][j-1]に 1 を加える代わりに、max(dp[i-1][j], dp[i][j-1])に 1 を加える。これでは同じ文字を 2 回使うことがある。aaとaの場合、1 ではなく 2 が返される。 - まだ読み取り中の行に書き込む。2 行を使う場合、上の行から取得するすべての値は
prevを参照し、cur[0]は 0 のままにする必要がある。 - Python で長さ 1000 の文字列に対して再帰をメモ化する。呼び出しの深さは 2000 に達し、デフォルトの上限である 1000 を超える。
よくある質問3
最長共通部分列の時間計算量はどれくらいですか？
表を使った解法の実行時間は O(n × m) で、各接頭辞のペアにつき1つのセルを処理します。表全体を保存するには O(n × m) のメモリが必要ですが、2行を使えば O(min(n, m)) で済みます。表を使わない単純な再帰は指数時間になります。
最長共通部分列と最長共通部分文字列の違いは何ですか？
部分列は順序を保つ限り文字を飛ばすことができますが、部分文字列は隣り合う文字のまとまりです。stone と longest の最長共通部分列は one (3) ですが、最長共通部分文字列は on (2) です。部分文字列の表では、不一致の場合、隣のセルをコピーする代わりにセルを 0 にリセットします。
LCSはdiffツールや編集距離とどのように関係していますか？
ファイルの2つのバージョン間の差分は、行の最長共通部分列を保持し、それ以外のすべての行を追加または削除として表示します。ある文字列を別の文字列に変換するために必要な挿入と削除の最小数は n + m - 2 × LCS です。編集距離では文字の置換も許されるため、独自の表が必要です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def longestCommonSubsequence(text1, text2):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
text1 = "stone" text2 = "longest"
期待される出力
3