【解説】アルゴリズムイントロダクション：15.4 最長共通部分列

定理 15.1 (LCS の部分構造最適性) は，最長共通部分列 (LCS) 問題が「最適部分構造」をもつことを示すものです。以下，定理の内容と具体例を通してその意味を解説します。

---

## 定理 15.1 の内容

文字列 $X = \langle x_1, x_2, \dots, x_m\rangle$ と
文字列 $Y = \langle y_1, y_2, \dots, y_n\rangle$ の LCS を $Z = \langle z_1, z_2, \dots, z_k\rangle$ とすると，次の３つの場合が成り立ちます。

1. **末尾が一致する場合**
   $x_m = y_n$ ならば，必ず

   $$
     z_k = x_m = y_n
   $$

   かつ

   $$
     \langle z_1, \dots, z_{k-1} \rangle
     \quad\text{は}
     \quad
     \mathrm{LCS}( \langle x_1,\dots,x_{m-1}\rangle,\;\langle y_1,\dots,y_{n-1}\rangle )
   $$

   となる。

2. **末尾が不一致で，LCS の末尾が $X$ の末尾ではない場合**
   $x_m \neq y_n$ かつ $z_k \neq x_m$ ならば，
   $Z$ は $\langle x_1,\dots,x_{m-1}\rangle$ と $Y$ の LCS。

3. **末尾が不一致で，LCS の末尾が $Y$ の末尾ではない場合**
   $x_m \neq y_n$ かつ $z_k \neq y_n$ ならば，
   $Z$ は $X$ と $\langle y_1,\dots,y_{n-1}\rangle$ の LCS。

これにより，文字列を末尾方向から「一文字ずつ削って考えれば」小問題に帰着できることがわかります。動的計画法で LCS を求める根拠がここにあります。

---

## 具体例で確認

以下の例で，各場合を確かめてみましょう。

* $X = \texttt{A B C B D A B}$
* $Y = \texttt{B D C A B A}$

これらの LCS のひとつは

$$
  Z = \langle \texttt{B}, \texttt{C}, \texttt{B}, \texttt{A}\rangle
  = \texttt{BCBA}
$$

（長さ 4）です。末尾同士を見てみます：

1. **末尾一致の場合**

   $$
     x_m = x_7 = \texttt{B},\quad y_n = y_6 = \texttt{A}
   $$

   ここでは $\texttt{B}\neq\texttt{A}$ なので該当せず。

2. **末尾不一致で $z_k \neq x_m$ の場合**

   * $x_m=\texttt{B}$, $z_k=\texttt{A}$ なので確かに $z_k\neq x_m$。
   * このとき，定理より

     $$
       Z = \texttt{BCBA}
       \quad\text{は}
       \quad
       \mathrm{LCS}(\langle\texttt{A B C B D A}\rangle,\;Y)
     $$

     すなわち $X$ の最後の文字 $\texttt{B}$ を除いた文字列と $Y$ の LCS であるはずです。

   実際，

   $$
     X'=\texttt{A B C B D A},\;Y=\texttt{B D C A B A}
   $$

   に対しても LCS は長さ 4 の “BCBA” になり，定理どおりです。

3. **末尾不一致で $z_k \neq y_n$ の場合**
   同様に $y_n=\texttt{A}$, $z_k=\texttt{A}$ なので今回は $z_k = y_n$ であり該当せず。

---

## 末尾一致の例

別の例として，次のように末尾文字が一致する場合を見てみましょう。

* $X = \texttt{A B C A}$
* $Y = \texttt{B C A}$

ここで末尾は両方とも $\texttt{A}$ なのでケース 1 に該当します。
LCS は “BCA”（長さ 3）で，末尾の $\texttt{A}$ が共通末尾です。
定理によれば，
“**BC**” は
$\langle \texttt{A B C}\rangle$ と $\langle \texttt{B C}\rangle$ の LCS であるはず。
実際に両方の LCS は “BC”（長さ 2）で一致します。

---

### まとめ

* **定理 15.1** は，LCS 問題の「最適部分構造」を保証するもの。
* 「末尾一致」「末尾だけ片方を捨てる」のいずれかで，問題を必ず小さくできる。
* これが動的計画法（テーブル計算）で LCS を効率的に求める理論的根拠となる。

具体例を通して確認すると，定理の３つのケースがいずれも成り立つことが直感的に理解できるはずです。


LCS を動的計画法で解く「第２段階」としては，問題を小さな部分問題に帰着させるための\*\*再起的な漸化式（recurrence relation）\*\*を定義します。以下のように説明できます。

---

## 1. 部分問題の定義

まず，長さ $i$ の接頭辞 $X[1..i]$ と，長さ $j$ の接頭辞 $Y[1..j]$ の LCS の長さを

$$
c[i][j] = \bigl|\mathrm{LCS}(X[1..i],\,Y[1..j])\bigr|
$$

と定義します。最終的に求めたいのは $c[m][n]$ です。

## 2. 境界条件（ベースケース）

* $i=0$ （空文字列と何か）の場合は共通部分列は空なので

  $$
  c[0][j] = 0 \quad(\forall j)
  $$
* 同様に $j=0$ の場合も

  $$
  c[i][0] = 0 \quad(\forall i)
  $$

## 3. 再起的な漸化式

文字 $x_i$ と $y_j$ の比較結果によって，次の２通りに場合分けします。

1. **末尾文字が一致するとき**（$x_i = y_j$）
   末尾の１文字を共通部分列に含められるので，

   $$
   c[i][j] = c[i-1][\,j-1\,] + 1
   $$

2. **末尾文字が不一致のとき**（$x_i \neq y_j$）
   いずれかの末尾文字をあきらめる（部分問題をひとつ短くする）ので，

   $$
   c[i][j] = \max\bigl(c[i-1][j],\;c[i][j-1]\bigr)
   $$

まとめると，

$$
c[i][j] =
\begin{cases}
0, & i=0 \text{ または } j=0,\\
c[i-1][j-1] + 1, & x_i = y_j,\\
\max\bigl(c[i-1][j],\,c[i][j-1]\bigr), & x_i \neq y_j.
\end{cases}
$$

---

## 4. なぜこの漸化式になるのか

* **一致する場合**：最後の文字を共通列の末尾に付け足せる。
* **不一致の場合**：両方の末尾を同時に捨てるわけにはいかないので，どちらか一方だけ捨てればいい。「どちらを捨てると LCS が長くなるか」を比べるために $\max$ をとる。

この再起的定義に従って，二重ループで $i=1..m$, $j=1..n$ を走査し，テーブル $c[i][j]$ を順次埋めていけば、最終的に $c[m][n]$ が求まり、かつ必要なら逆向きに復元して実際の LCS 文字列も得られます。

---

### 小さな例

たとえば

$$
X=\texttt{ABCBDAB},\quad Y=\texttt{BDCABA}
$$

を考えると，$i=3,j=2$ （$X[1..3]=\texttt{ABC}$, $Y[1..2]=\texttt{BD}$）では

* 末尾文字は $\texttt{C}$ vs. $\texttt{D}$ で **不一致** ⇒

  $$
  c[3][2] = \max\bigl(c[2][2],\,c[3][1]\bigr)
           = \max(1,\,1) = 1.
  $$

こうしてテーブルを埋めることで，最終的に $c[7][6]=4$（LCS “BCBA” など）となります。

---

以上が，第２段階における「再起的な解の漸化式」の説明です。


以下に，第３段階として動的計画法で LCS の長さを求める擬似コード（LCS-Length）と，なぜその実行時間が $O(mn)$ になるかを丁寧に説明します。ここで文字列の長さをそれぞれ $X$ が長さ $m$，$Y$ が長さ $n$ とします。

---

## LCS-Length の擬似コード

```text
LCS-Length(X[1..m], Y[1..n])
  // c は (m+1)×(n+1) の配列（0..m, 0..n を使う）
  for i ← 0 to m
    c[i][0] ← 0
  for j ← 0 to n
    c[0][j] ← 0

  for i ← 1 to m
    for j ← 1 to n
      if X[i] = Y[j] then
        c[i][j] ← c[i−1][j−1] + 1
      else
        c[i][j] ← max( c[i−1][j], c[i][j−1] )

  return c  // c[m][n] が LCS の長さ
```

* **配列サイズ**：行が $0,1,\dots,m$、列が $0,1,\dots,n$ の計 $(m+1)\times(n+1)$ 要素
* **境界初期化**：どちらか一方が空文字列（長さ0）なら LCS 長さは 0
* **再帰から反復へ**：前段階の漸化式を，二重ループで順番にテーブルに書き込む

---

## 実行時間解析

1. **境界初期化のコスト**

   * $i=0$ を固定して $j=0..n$ を初期化：$n+1$ 回の代入
   * $j=0$ を固定して $i=0..m$ を初期化：$m+1$ 回の代入
     いずれも $O(m+n)$

2. **メインの二重ループ**

   ```text
   for i ← 1 to m
     for j ← 1 to n
       【一定時間の操作】
   ```

   * 外側ループは $i=1,2,\dots,m$ の $m$ 回
   * 内側ループは $j=1,2,\dots,n$ の $n$ 回
   * 各ループの中身は文字比較 `X[i] = Y[j]`＋配列参照と代入、あるいは２つの数の比較と代入。いずれも $O(1)$

   したがって，メインループ全体で要する基礎操作の総数は

   $$
     m \times n \times O(1) = O(mn).
   $$

3. **全体コスト**
   境界初期化 $O(m+n)$ とメインループ $O(mn)$ を合わせても，支配項は $O(mn)$ なので

   $$
     \text{LCS-Length の時間計算量} = O(mn).
   $$

---

## 空間利用について（おまけ）

* 上記コードでは $(m+1)\times(n+1)$ のテーブルを使うため，空間計算量は $O(mn)$
* 空間を $O(\min(m,n))$ に削減する工夫もありますが，まずはこの基本形で理解するのが標準です

---

### まとめ

* **コード**：二重ループで漸化式をテーブルに書き込み
* **時間計算量**：ループの反復回数が $m$ × $n$ 回で，各反復は定数時間 ⇒ $O(mn)$
* 動的計画法の典型例として，文字列長の積に比例した効率的アルゴリズムです。