Educational DP Contest F
\(s\) の \(i\) 文字目と \(t\) の \(j\) 文字目まで見たときの最長一致部分列の最大値を \(A(i, j)\) とすると,
\(s_i = t_j\) のとき:
\[A(i, j) = \max(A(i-1, j), A(i, j-1), A(i-1, j-1)+1)\]\(s_i \neq t_j\) のとき:
\[A(i, j) = \max(A(i-1, j), A(i, j-1))\]となる.
これで最大値を求めた後, その文字列を復元する. \(A(\vert s \vert, \vert t \vert)\) からスタートして, \(A(0, 0)\) までたどり着くルートを考える.
\(A(i, j)\) にいるとき,
- \(A(i-1, j) = A(i, j)\) ならば移動できる.
- \(A(i, j-1) = A(i, j)\) ならば移動できる.
- \(A(i-1, j-1) = A(i, j)-1\) ならば移動できる. このとき, \(s_i(=t_j)\) の文字は部分列の要素である.
という感じで部分列の要素を拾っていけば部分列を再生できる.
計算量は \(O(\vert s \vert \vert t \vert)\) である.