algorithm - 線形メモリ使用量の最長共通サブシーケンス

Question

私はメモリの線形空間を使用するアルゴリズムを見つけようとしています:

任意のアルファベットの 2 つの文字列 x と y が与えられた場合、それらの最長の共通サブ シーケンスを決定します。

Answer 1

LCS 問題を解決するために動的計画法のソリューションでテーブルの次の行を計算する場合、前の行と現在の行のみが必要であることに注意してください。次に、動的計画法ソリューションを変更して、mxn テーブルではなく前の行と現在の行のみを追跡できます。現在の行の最後に到達するたびに、前の行を現在の行に設定し、行の先頭からもう一度開始します。これを m 回行います。ここで、m はテーブル内の行数です。これにより、列数に比例してスペースが使用されます。