アルゴリズムと計算量の問題

$X=x_1{x}_2\cdots x_6=\mathrm{C}\mathrm{A}\mathrm{B}\mathrm{D}\mathrm{A}\mathrm{B}$、$Y=y_1{y}_2\cdots y_6=\mathrm{A}\mathrm{B}\mathrm{C}\mathrm{A}\mathrm{D}\mathrm{B}$ とする。

方針. $X$ の先頭 $i$ 文字と $Y$ の先頭 $j$ 文字の最長共通部分列の長さを $L(i,j)$、その最長共通部分列（文字列）全体の集合を $S(i,j)$ とする。$L(i,0)=L(0,j)=0$、$S(i,0)=S(0,j)=\{\epsilon \}$（$\epsilon$ は空文字列）である。

• $x_i=y_j$ のとき：$L(i,j)=L(i-1,j-1)+1$ であり、どの最長共通部分列も最後の文字を $x_i$ と $y_j$ に対応させるように取り直せるので、$S(i,j)=\{s{x}_i:s\in S(i-1,j-1)\}$。
• $x_i\ne y_j$ のとき：$x_i$ と $y_j$ の少なくとも一方は使われないので $L(i,j)=\max \{L(i-1,j),L(i,j-1)\}$ であり、$S(i,j)$ は $S(i-1,j)$ と $S(i,j-1)$ のうち長さが $L(i,j)$ に等しいほうの和集合（等しければ両方の和集合）。

長さの表 $L(i,j)$（行が $i$、列が $j$）:

よって最長共通部分列の長さは $L(6,6)=4$。

集合の表 $S(i,j)$:

• $i=1$ (C): $\{\epsilon \},\{\epsilon \},\{\mathrm{C}\},\{\mathrm{C}\},\{\mathrm{C}\},\{\mathrm{C}\}$
• $i=2$ (A): $\{\mathrm{A}\},\{\mathrm{A}\},\{\mathrm{A},\mathrm{C}\},\{\mathrm{CA}\},\{\mathrm{CA}\},\{\mathrm{CA}\}$
• $i=3$ (B): $\{\mathrm{A}\},\{\mathrm{AB}\},\{\mathrm{AB}\},\{\mathrm{AB},\mathrm{CA}\},\{\mathrm{AB},\mathrm{CA}\},\{\mathrm{CAB}\}$
• $i=4$ (D): $\{\mathrm{A}\},\{\mathrm{AB}\},\{\mathrm{AB}\},\{\mathrm{AB},\mathrm{CA}\},\{\mathrm{ABD},\mathrm{CAD}\},\{\mathrm{CAB},\mathrm{ABD},\mathrm{CAD}\}$
• $i=5$ (A): $\{\mathrm{A}\},\{\mathrm{AB}\},\{\mathrm{AB}\},\{\mathrm{ABA}\},\{\mathrm{ABA},\mathrm{ABD},\mathrm{CAD}\},\{\mathrm{CAB},\mathrm{ABD},\mathrm{CAD},\mathrm{ABA}\}$
• $i=6$ (B): $\{\mathrm{A}\},\{\mathrm{AB}\},\{\mathrm{AB}\},\{\mathrm{ABA}\},\{\mathrm{ABA},\mathrm{ABD},\mathrm{CAD}\},S(6,6)$

例えば $S(4,5)$ は $x_4=y_5=\mathrm{D}$ なので $S(3,4)=\{\mathrm{AB},\mathrm{CA}\}$ の各要素に D を付けて $\{\mathrm{ABD},\mathrm{CAD}\}$、$S(5,4)$ は $x_5=y_4=\mathrm{A}$ なので $S(4,3)=\{\mathrm{AB}\}$ に A を付けて $\{\mathrm{ABA}\}$ となる。

最後に $x_6=y_6=\mathrm{B}$ なので
$$S(6,6)=\{s\mathrm{B}:s\in S(5,5)\}=\{\mathrm{ABAB},\mathrm{ABDB},\mathrm{CADB}\}.$$

確認：$\mathrm{ABAB}$ は $X$ の $2,3,5,6$ 文字目、$Y$ の $1,2,4,6$ 文字目。$\mathrm{ABDB}$ は $X$ の $2,3,4,6$ 文字目、$Y$ の $1,2,5,6$ 文字目。$\mathrm{CADB}$ は $X$ の $1,2,4,6$ 文字目、$Y$ の $3,4,5,6$ 文字目。

したがって、最長共通部分列は文字列として $3$ 通りである。

動的計画法で $L[i][j]$（$X$ の先頭 $i$ 文字と $Y$ の先頭 $j$ 文字の LCS の長さ）を計算する。$X=\mathrm{CABDAB}$、$Y=\mathrm{ABCADB}$ のとき、表は次のようになる。

• $i=1$: 0,0,1,1,1,1
• $i=2$: 1,1,1,2,2,2
• $i=3$: 1,2,2,2,2,3
• $i=4$: 1,2,2,2,3,3
• $i=5$: 1,2,2,3,3,3
• $i=6$: 1,2,2,3,3,4

よって LCS の長さは $4$ である。

次に、$S(i,j)$ を先頭 $i$ 文字と先頭 $j$ 文字の LCS 全体の集合として、表をたどり直して文字列としての重複を除きながら列挙する。

• $S(6,6)$: $X_6=Y_6=\mathrm{B}$ なので $S(5,5)+\mathrm{B}$。
• $S(5,5)$: $X_5=\mathrm{A}$、$Y_5=\mathrm{D}$ で異なり、$L[4][5]=L[5][4]=3$ なので $S(4,5)\cup S(5,4)$。
• $S(4,5)$: $X_4=Y_5=\mathrm{D}$ なので $S(3,4)+\mathrm{D}$。
• $S(3,4)=S(2,4)\cup S(3,3)=\{\mathrm{CA}\}\cup \{\mathrm{AB}\}$。
• したがって $S(4,5)=\{\mathrm{CAD},\mathrm{ABD}\}$。
• $S(5,4)$: $X_5=Y_4=\mathrm{A}$ なので $S(4,3)+\mathrm{A}$。
• $S(4,3)=\{\mathrm{AB}\}$ なので $S(5,4)=\{\mathrm{ABA}\}$。
• よって $S(5,5)=\{\mathrm{CAD},\mathrm{ABD},\mathrm{ABA}\}$ となり、$S(6,6)=\{\mathrm{CADB},\mathrm{ABDB},\mathrm{ABAB}\}$。

検算として、3 つとも両方の部分列になっていることを確かめる。

• CADB: $X$ の位置 1,2,4,6、$Y$ の位置 3,4,5,6。
• ABDB: $X$ の位置 2,3,4,6、$Y$ の位置 1,2,5,6。
• ABAB: $X$ の位置 2,3,5,6、$Y$ の位置 1,2,4,6。

したがって答えは $3$ 通り。