アルゴリズムと計算量の問題
文字列 から 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を、 の部分列という（取り除く文字は連続していなくてよい）。
つの文字列
を考える。 と がどちらも の部分列となるような文字列 （ と の共通超列）のうち、長さが最小のものの長さを求めよ。
この問題で使うもの
- 最長共通部分列（説明と入口の問題）
この問題を解けるようになるまで（2 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
最短共通超列の長さは、 と の最長共通部分列（LCS）の長さ を使って と表せます。まず LCS の長さを求めましょう。
ヒント 2
を の先頭 文字と の先頭 文字の LCS の長さとすると、 なら 、そうでなければ です。
ヒント 3
表を埋めると、 の先頭 文字 と 全体の LCS の長さは 、 の先頭 文字 と の先頭 文字 の LCS の長さは になります。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
方針. 長さ の文字列 と長さ の文字列 の最短共通超列の長さは である。ここで は と の最長共通部分列（LCS）の長さである。
理由: 共通超列 の中で を部分列として取り出すときに使う文字の位置と、 を取り出すときに使う文字の位置を決めておく。両方で使われる位置の文字を順に並べると と の共通部分列になるので、その個数は 以下である。 の長さは少なくとも「 で使う位置の数」と「 で使う位置の数」の和から「両方で使う位置の数」を引いたものなので、。逆に、LCS の 文字を 回ずつ使い、その間に と の残りの文字を順に挿入すれば長さ の共通超列が作れる。
LCS の動的計画法. を の先頭 文字と の先頭 文字の LCS の長さとし、 とする。 について
で表を埋める。（行）、（列）として計算すると次のようになる。
よって である。実際、 は の 文字目、 の 文字目として現れる共通部分列である。
答え. 最短共通超列の長さは
例えば、LCS を骨組みにして、（ のみ）, （ のみ）, （共通）, （ のみ）, （ のみ）, （共通）, （ のみ）, （共通）, （共通）, （ のみ）と並べると、（長さ ）が得られる。 の 文字目を取り出すと 、 文字目を取り出すと になるので、確かに共通超列である。
別解
最短共通超列の長さは で与えられる（LCS は最長共通部分列の長さ）。 なので LCS を動的計画法で求める。
を の先頭 文字と の先頭 文字の LCS 長とし、 なら 、そうでなければ 。 の列に対し各行は
- D:
- B:
- A:
- C:
- B:
- A:
- D:
よって LCS の長さは （例: 。 の 2,4,6,7 文字目、 の 2,4,5,6 文字目）。
最短共通超列の長さは 。