解説
dpテーブルを以下のように定義します。
- 長さ の文字列で、最後の 文字が、 の最初の 文字と一致しているものの個数
ただし、 はできるだけ大きい値をとるようにする必要があります。
例えば、 のとき、文字列 の最後の 文字と の最初の 文字が一致しているとも考えられますが、
最後の 文字が の最初の 文字と一致していると考えます。
遷移は以下のようになります。
ここで、 は かつ を満たす最大の です。
配列 を で前計算した上で、dpテーブルの更新は で行うことができます。