じゅぴろの日記(⋈◍＞◡＜◍)。✧♡

MP法を用いて、goalの前 文字に文字 を加えた文字列のsuffixがgoalのprefixと何文字一致するかを前計算します。 後のDPは簡単で、計算量は です 追記(DPパート) 簡単でで説明を省略しない！ということで簡単に スタートから に行くまでの期待値 とします。 における変化を考えます。 文字目の目が であったとしましょう。 …