解説


dpテーブルを以下のように定義します。

  • 長さ の文字列で、最後の 文字が、 の最初の 文字と一致しているものの個数

ただし、 はできるだけ大きい値をとるようにする必要があります。

例えば、 のとき、文字列 の最後の 文字と の最初の 文字が一致しているとも考えられますが、
最後の 文字が の最初の 文字と一致していると考えます。

遷移は以下のようになります。

ここで、 かつ を満たす最大の です。
配列 で前計算した上で、dpテーブルの更新は で行うことができます。