最長共通部分列
DP テーブルで 2 つの文字列を対応付けます
「最長共通部分列」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
部分列とは
部分列は文字の順序を保ちますが、一部の文字を飛ばしてもかまいません。'abcde' から 'ace' は選べますが、'aec' は選べません。
LCSの目的
2つの文字列が与えられたとき、最長共通部分列とは、両方に同じ相対的な順序で現れる最長の列です。
グリッドに置き換える
2つの文字列の接頭辞を比較します。文字列の長さに対応する2Dのテーブルを使うと、これをおなじみのグリッドDPに変換できます。
状態を定義する
dp[i][j]を、A の最初の i 文字と B の最初の j 文字に対するLCSの長さとします。
文字が一致する場合
A[i-1] と B[j-1] が等しい場合、その共通する文字がLCSを1つ伸ばします。対角の値 dp[i-1][j-1] に1を加えます。
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1文字が異なる場合
文字が異なる場合は、どちらか一方の文字を捨てて、よりよい結果を残します。2つの隣接セルのmaxを取ります。
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])初期条件
空の接頭辞には共通するものがないため、LCSの長さは0です。0行目と0列目はすべて0のままにします。
dp = [[0] * (m+1) for _ in range(n+1)]行と列を1つずつ余分に用意する
n+1 行、m+1 列のテーブルにすると、0で埋まった境界を用意できます。これにより、端で煩雑な範囲チェックをせずに済みます。
テーブルを埋める
i と j を1から増やしながらループします。各セルが必要とするのは上、左、対角の値だけで、それらはすでに計算済みです。
for i in range(1, n+1):
for j in range(1, m+1):
...長さを読み取る
完全なLCSの長さは右下のセルに入ります。すべてのセルを埋めた後の答えは dp[n][m] です。
length = dp[n][m]計算量
すべてのセルを1回ずつ扱うため、時間計算量とメモリ計算量はともにO(n times m)です。数千文字程度の文字列なら十分に処理できます。
クイックチェック
現在の文字 A[i-1] と B[j-1] は等しいとします。正しい更新はどれでしょうか。
まとめ：LCS
n+1 行、m+1 列のテーブルを作ります。一致した場合は対角の値に1を加え、それ以外では隣接セルのmaxを取ります。右下のセルに長さが入ります。🔗
よくある質問
「最長共通部分列」レッスンは無料ですか？
はい。「最長共通部分列」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「最長共通部分列」で何を学びますか？
DP テーブルで 2 つの文字列を対応付けます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「最長共通部分列」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。