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

$Y$ の部分列の形 $Y$ は $\mathrm{c}$ が $n$ 個、$\mathrm{b}$ が $n$ 個、$\mathrm{a}$ が $n$ 個の順に並んだ文字列なので、その部分列は
$${\mathrm{c}}^i{\mathrm{b}}^j{\mathrm{a}}^k(0\le i,j,k\le n)$$
（$\mathrm{c}$ を $i$ 個、$\mathrm{b}$ を $j$ 個、$\mathrm{a}$ を $k$ 個この順に並べた文字列）の形に限られ、この形の文字列はすべて $Y$ の部分列である。したがって共通部分列は、この形の文字列のうち $X$ の部分列になるものである。

長さは $n$ 以下 $X$ を $3$ 文字ずつ区切った $t$ 番目の $\mathrm{abc}$ を第 $t$ ブロックとよぶ（$t=1,\dots ,n$）。各ブロックの中では、$\mathrm{a}$ が $1$ 文字目、$\mathrm{b}$ が $2$ 文字目、$\mathrm{c}$ が $3$ 文字目にある。

${\mathrm{c}}^i{\mathrm{b}}^j{\mathrm{a}}^k$ を $X$ の部分列として取り出すとき、隣り合う $2$ 文字（前の文字・次の文字）の組は
$$\mathrm{cc},\mathrm{cb},\mathrm{ca},\mathrm{bb},\mathrm{ba},\mathrm{aa}$$
のどれかである（$\mathrm{ca}$ は $j=0$ のときに現れる）。どの組でも、次の文字のブロック内の位置（$\mathrm{a}$ なら $1$, $\mathrm{b}$ なら $2$, $\mathrm{c}$ なら $3$）は、前の文字のブロック内の位置以下である。一方、部分列として取り出すには、次の文字を $X$ の中で前の文字より真に右から取らなければならない。もし $2$ 文字が同じブロックにあれば、次の文字はブロック内で前の文字より真に右、つまりブロック内の位置が真に大きくなければならず、上のことに反する。よって、次の文字は前の文字より真に後ろのブロックから取らなければならない。

したがって取り出す文字はすべて異なるブロックにあり、ブロックは $n$ 個なので
$$i+j+k\le n.$$

長さ $n$ は実現できる $i+j+k=n$ となる $0$ 以上の整数 $i,j,k$ に対し、第 $1$〜$i$ ブロックからは $\mathrm{c}$、第 $i+1$〜$i+j$ ブロックからは $\mathrm{b}$、第 $i+j+1$〜$n$ ブロックからは $\mathrm{a}$ を $1$ 個ずつ取れば、${\mathrm{c}}^i{\mathrm{b}}^j{\mathrm{a}}^k$ が $X$ の部分列として得られる。また $i,j,k\le n$ なので $Y$ の部分列でもある。

以上より、最長共通部分列の長さは $n$ であり、最長共通部分列は $i+j+k=n$ を満たす ${\mathrm{c}}^i{\mathrm{b}}^j{\mathrm{a}}^k$ のすべてである。$(i,j,k)$ が異なれば文字列も異なるので、その個数は $i+j+k=n$ を満たす $0$ 以上の整数の組 $(i,j,k)$ の個数、すなわち $3$ 種類から重複を許して $n$ 個選ぶ重複組合せの数
$$\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)=\frac{(n+1)(n+2)}{2}$$
である。

（確認）$n=1$ のとき $X=\mathrm{abc}$, $Y=\mathrm{cba}$ で、最長共通部分列の長さは $1$、最長共通部分列は $\mathrm{a},\mathrm{b},\mathrm{c}$ の $3$ 通り。式の値 $\frac{2\cdot 3}{2}=3$ と一致する。$n=2$ のときは $\mathrm{cc},\mathrm{cb},\mathrm{ca},\mathrm{bb},\mathrm{ba},\mathrm{aa}$ の $6$ 通りで、式の値 $\frac{3\cdot 4}{2}=6$ と一致する。

$Y={\mathrm{c}}^n{\mathrm{b}}^n{\mathrm{a}}^n$ の部分列は ${\mathrm{c}}^i{\mathrm{b}}^j{\mathrm{a}}^k$（$0\le i,j,k\le n$）の形に限る。これが $X=(\mathrm{abc}{)}^n$ の部分列になる条件を調べる。

$X$ の第 $m$ ブロック（$m=1,\dots ,n$）は a, b, c の順。${\mathrm{c}}^i$ を最も左に取ると第 $1$〜$i$ ブロックの c を使う。次の b は、同じブロックの b は c より左にあるので使えず、第 $i+1$ ブロック以降から取る。よって ${\mathrm{b}}^j$ は第 $i+1$〜$i+j$ ブロック。同様に直前の b の次の a は次のブロックの a なので、${\mathrm{a}}^k$ は第 $i+j+1$〜$i+j+k$ ブロック。これが $X$ に収まる条件は $i+j+k\le n$（ある文字の個数が 0 のときも同じ式）。

したがって共通部分列の長さは高々 $n$ で、$n$ になるのは $i+j+k=n$ のときで、そのとき必ず存在する（例: 全部 c など）。最長共通部分列は ${\mathrm{c}}^i{\mathrm{b}}^j{\mathrm{a}}^k$（$i+j+k=n$, $i,j,k\ge 0$ の整数）で、$(i,j,k)$ が異なれば文字列も異なる。

個数は非負整数解の個数 $\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)=\frac{(n+1)(n+2)}{2}$。

検算: $n=1$: $X=\mathrm{abc}$, $Y=\mathrm{cba}$、最長共通部分列は a, b, c の 3 通り。式は $\frac{2\cdot 3}{2}=3$ で一致。