私は先週 LCS 問題を勉強していて、質問があります。
最長のサブシーケンス自体 (長さだけでなく) を見つけることにも関心があるときはいつでも、補助 (string1.length X string2.length) 行列を作成し、上矢印、左矢印、または斜め矢印を追加してサブシーケンスを決定します。 、元の場所に対応するため、後で手順をたどってサブシーケンス自体を見つけることができます。
(ここで例を参照してください: http://www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdfの最後のページ)
私の質問は次のとおりです。次の 2 つの文字列を実行するための次の出力マトリックスを検討してください。
- 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 1 1 1 1
- 0 0 0 0 0 0 0 1 2 2 2
- 0 0 0 0 0 0 0 1 2 3 3
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 2 2 2 2 3 4
空間の複雑さを増やさなくても、マトリックスの最後の列だけに基づいて、共通のサブシーケンスを見つけることができるというのは本当ですか?