問題 No.3376
文字列 $X = \text{"ABCBDAB"}$ と文字列 $Y = \text{"BDCABA"}$ に対する最長共通部分列 (LCS) の長さを求める。LCSの長さとして、正しいものはどれか。
【正解の解説】
$4$
これは、2冊の本から偶然一致するフレーズを探すようなものです。連続していなくても良いので、文字の順番を守りながら「B」「C」「B」「A」という4文字を両方の文字列から抽出できるため、長さが4になります。日常で言えば、複数のメモから共通する重要な予定だけを時系列順に抜き出す作業に似ています。
スポンサーリンク
【その他の選択肢の解説】
$3$
真面目に全通りを検証せず、目についた一致箇所だけを拾って満足してしまうと、この短い数値を誤って選んでしまいます。LCSは「最も長い」組み合わせを探すアルゴリズムなので、途中で探索をやめずにすべての可能性を考慮することが不可欠です。
$5$
人間の目は都合よく文字を繋げてしまう癖があり、実際には存在しない「BCABA」のような幻の共通列を作ってしまうことでこのミスが生まれます。焦って解くと文字列の重複に惑わされるため、動的計画法のような確実な表埋め手順で冷静に確認するスキルが試されます。
$6$
文字列Xの長さは7、Yの長さは6であり、共通部分列の長さが相手の文字数を超えることは絶対にありません。初学者がやりがちな「とりあえず大きめの数字を選んでおく」という勘ぐりを誘うための典型的なひっかけ選択肢となっています。