Codeforces Round #338 (Div. 2) C. Running Track

次のような DP で解ける。

t[i..] の先頭 L 文字が s または rev(s) に含まれていれば dp[i] から dp[i+1]～dp[i+L] に遷移できる。s と t の LCP は O(|s||t|) の DP で計算できるので、これを使って最大の L を O(|s||t|) で計算しよう。

DP の復元が必要なので実装は辛い。

Good bye コンテストで得た知識を使えて嬉しい。でもコンテスト中に通したかった。