令和7年度 秋期 応用情報技術者試験 午後 問題 問3 動的計画法による最長共通部分列

二つの列の最長共通部分列 (Longest Common Subsequence) の長さを求めるアルゴリズムに関する次の記述を読んで，設問に答えよ。

列 $X=\{x_1, x_2, \dots, x_n\}$ に対して，順序を保持して要素を抽出した列を部分列という。また，列の長さはその列の要素の個数で定義される。ここでは，各要素が文字である列を考える。例えば，$X=\{\text{“A”}, \text{“B”}, \text{“C”}, \text{“B”}, \text{“D”}, \text{“A”}, \text{“B”}\}$ のとき，図1に示すように $\{\text{“B”}, \text{“C”}, \text{“D”}, \text{“B”}\}$ は $X$ の部分列の例であり，その長さは4である。

ある列 $Z$ が二つの列 $X, Y$ 両方の部分列であるとき，$Z$ を $X$ と $Y$ との共通部分列といい，共通部分列のうち長さが最大となるものを最長共通部分列という。最長共通部分列は複数通り存在する場合もあるが，その長さは一意に決まる。$X=\{\text{“A”}, \text{“B”}, \text{“C”}, \text{“B”}, \text{“D”}, \text{“A”}, \text{“B”}\}, Y=\{\text{“B”}, \text{“D”}, \text{“C”}, \text{“A”}, \text{“B”}, \text{“A”}\}$ の場合の共通部分列及び最長共通部分列の例を図2に示す。

なお，共通部分列が存在しない場合，最長共通部分列は空の列となり，その長さは0である。
最長共通部分列の長さは，2本のDNAの塩基配列間の類似度を測る目的などに用いられる。

〔最長共通部分列の長さを求めるアルゴリズム〕

二つの列 $X, Y$ の最長共通部分列の長さを求めるアルゴリズムを考える。列 $X, Y$ それぞれについて，先頭から $n$ 個，$k$ 個の要素を抽出した列を $X_n, Y_k$ と表記し，列 $X_n, Y_k$ それぞれの末尾の要素を $x_n, y_k$ と表記する。例えば，$X=\{\text{“A”}, \text{“B”}, \text{“C”}, \text{“B”}\}$ とすると，$X_3=\{\text{“A”}, \text{“B”}, \text{“C”}\}, x_3=\text{“C”}$ である。このとき，列 $X_n$ と列 $Y_k$ との最長共通部分列の中の一つを $LCS(n, k)$，最長共通部分列の長さを $LCSL(n, k)$ と表記する。なお，$X_0$ と $Y_0$ は空の列であり，$x_0$ と $y_0$ は存在しない。

ここで，$x_n$ と $y_k$ とが一致しているか否かに着目して次の1.〜3.に場合分けし，再帰的な関係を用いて $LCSL(n, k)$ を求めることを考える。

1. $x_n=y_k$ の場合を考える。例えば，$x_n=y_k=\text{“A”}$ とする。このとき，$LCS(n, k)$ の末尾の要素は “A” となる。よって，$LCS(n, k)$ は，列 $X_{n-1}, Y_{k-1}$ の最長共通部分列 $LCS(n-1, k-1)$ の末尾に “A” を付加したものと一致する。したがって，$LCSL(n, k) = LCSL(n-1, k-1) + 1$ が成り立つ。
2. $x_n \neq y_k$ の場合を考える。例えば，$x_n=\text{“A”}, y_k=\text{“B”}$ とする。ここで，$LCS(n, k)$ の末尾の要素は “A” 又は “A” 以外となる。$LCS(n, k)$ の末尾の要素が “A” である場合は，列 $Y_k$ から末尾の “B” を取り除いても最長共通部分列には影響しないので，$LCS(n, k)$ は $LCS(n, k-1)$ と一致する。一方，$LCS(n, k)$ の末尾の要素が “A” でない場合は，列 $X_n$ から末尾の “A” を取り除いても最長共通部分列には影響しないので，$LCS(n, k)$ は $LCS(n-1, k)$ と一致する。よって，$LCS(n, k)$ は $LCS(n, k-1)$ 又は $LCS(n-1, k)$ のいずれかと一致する。したがって，$LCSL(n, k)$ は，$LCSL(n, k-1)$ と $LCSL(n-1, k)$ のうちの最大値と一致する。
3. $n=0$ 又は $k=0$ の場合，最長共通部分列は空の列となり，$LCSL(n, k)=0$ である。

〔動的計画法を用いて最長共通部分列の長さを求めるアルゴリズム〕

1.〜3.の再帰的な関係に従い，$LCSL(n, k)$ を再帰的に計算することによって，列 $X, Y$ の最長共通部分列の長さを求めることができる。しかし，再帰的に計算するアルゴリズムでは，重複して同じ計算をすることによって時間計算量が大きくなり，非効率になる場合がある。そこで，重複して同じ計算をすることを避けるために，$LCSL(n, k)$ の値を動的計画法によって求めることを考える。

二つの列が $X=\{\text{“A”}, \text{“B”}, \text{“C”}, \text{“B”}, \text{“D”}, \text{“A”}, \text{“B”}\}, Y=\{\text{“B”}, \text{“D”}, \text{“C”}, \text{“A”}, \text{“B”}, \text{“A”}\}$ の場合，$0 \le n \le 7$ かつ $0 \le k \le 6$ に対する $LCSL(n, k)$ の値を図3に示す。図3の左端2列は $n$ (0〜7)とそれに対応する $x_n$ を，上端2行は $k$ (0〜6)とそれに対応する $y_k$ を表す。$n=0$ のときの $x_n$，$k=0$ のときの $y_k$ は存在しないので，“-”と表す。各要素は列 $X_n$ と列 $Y_k$ との最長共通部分列の長さ $LCSL(n, k)$ の値を示している。

図3の各要素の値は，〔最長共通部分列の長さを求めるアルゴリズム〕の1.〜3.の再帰的な関係に従って求められる。
まず，$n=0$ 又は $k=0$ のときは3.に対応するので，$LCSL(n, k)=0$ である。
それ以外の値について，例えば，図3の①〜③は次のように値が決まる。

• ①について，$x_2=y_1$ なので1.に対応し，$LCSL(2, 1) = LCSL(1, 0) + 1$ である。$LCSL(1, 0)=0$ なので，$LCSL(2, 1)=1$ となる。
• ②について，$x_2 \neq y_2$ なので2.に対応し，$LCSL(2, 1)=1, LCSL(1, 2)=0$ なので，$LCSL(2, 2)=1$ となる。
• ③について，$x_6 \neq y_2$ なので2.に対応し，$LCSL(6, 1)=1, LCSL(5, 2)=2$ なので，$LCSL(6, 2)=2$ となる。

図3の要素の値を全て計算することによって列 $X, Y$ の最長共通部分列の長さが4であると分かる。

〔動的計画法を用いて最長共通部分列の長さを求めるプログラム〕

〔動的計画法を用いて最長共通部分列の長さを求めるアルゴリズム〕に基づいて，二つの列の最長共通部分列の長さを求めるプログラムを考える。任意の二つの列をそれぞれ配列 S，T として受け取り，動的計画法を用いて最長共通部分列の長さを求めるプログラムを図4に示す。ここで，配列の要素番号は0から始まり，整数型の二次元配列 lcsl は，行番号が0から配列 S の要素数 $s$ までの $(s + 1)$ 行，列番号が0から配列 T の要素数 $t$ までの $(t + 1)$ 列の大きさをもつ。

○整数型: calculate_lcsl(文字型の配列: S, 文字型の配列: T)
整数型: s ← Sの要素数
整数型: t ← Tの要素数
整数型の二次元配列: lcsl ← {(s + 1)行, (t + 1)列の未定義の値}
整数型: n, k
for (nを0からsまで1ずつ増やす)
  lcsl[n, 0] ← 0
endfor
for (kを0からtまで1ずつ増やす)
  lcsl[0, k] ← 0
endfor
for (nを1からsまで1ずつ増やす)
  for (kを1からtまで1ずつ増やす)
    if (S[n - 1]がT[k - 1]と等しい)
      lcsl[n, k] ← <span id="q3_blank_u" class="blank-label">ウ</span>
    elseif (lcsl[n, k - 1]がlcsl[n - 1, k]より大きい)
      lcsl[n, k] ← <span id="q3_blank_e" class="blank-label">エ</span>
    else
      lcsl[n, k] ← <span id="q3_blank_o" class="blank-label">オ</span>
    endif
  endfor
endfor
return <span id="q3_blank_ka" class="blank-label">カ</span>

図4のプログラムの時間計算量を，配列 S の要素数 $s$，配列 T の要素数 $t$ を用いて表すと $O($キ$)$ である。