ABC211 C chokudai
この問題は典型的な動的計画法(DP)の問題である. ここで, $ T = "chokudai"とおく. すると, $ dp_{i, j} := 1-indexedで, $ Sの$ i文字目まで見て,$ Tの$ j文字目までの文字を順に選ぶ場合の数 とおいて, $ dp_{i, j}から$ dp_{i + 1, j + 1}($ Sの$ i + 1文字目と$ Tの$ j + 1文字目が等しい場合)と$ dp_{i + 1, j}(すべての場合)にそれぞれ遷移することで答えは$ dp_{|S|, |T|}の値となる.
よって, この問題を$ O(|S||T|)で解くことができた. $ |S| \leq 10^5, |T| = 8なので, これは十分高速である.