Educational Codeforces #21 G: Anthem of Berland

上図は3番目の入力例の文字列t="abcab"にダミーの1文字を加えたt+'#'="abcab#"に対してKMP法のDFAを描いたもの。!はその他の文字を表す。
tはオーバーラップしてもよいので、最終状態からの遷移もほしい。そこで、末尾にダミーの文字を加えた。これにより、最終状態からの遷移も得られた。
例えば
abcabと最後まで一致した後、
cが来た場合
接頭辞abcと一致するはず。実際、上図でそのような遷移が得られる。
|s|*|t|<=10^7という特殊な制約に注意しよう。
これにより、KMP法の計算以外ではO(|s|*|t|)の実行時間が許されている。
dp[i][j]を「Sの文字列をi番目まで確定していてDFA上で状態がjであるときの、DFA上のダミーでない最終状態に到達した回数の最大値」
とすれば、max(dp[|s|][j])が解。