[AOJ] No. 0341 繰り返す呪文

問題

方針

動的計画法を行います。\( d(i, j) \) を \( t \) の \( j \) 番目までの部分文字列において、\( b \) の \( j \) 番目までの部分文字列の出現回数とします。初期値は、\( d(i, 0) = 1 \ ( 0 \leq i \leq |t|) \) とします。更新式は以下となります。

  • \( t_i = b_j \) のとき

\[d(i + 1, j + 1) = d(i, j + 1) + d(i, j)\]

  • \( t_i \neq b_j \) のとき

\[d(i + 1, j + 1) = d(i, j + 1)\]

\( d(|t|, |b|) \) が答えとなります。

コード