pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CSAcademy #20 Palindromic Concatenation

https://csacademy.com/contest/round-20/#task/palindromic-concatenation

解法

文字列 S と文字列 T を結合して回文になる条件を考えてみよう。|S|>|T|のとき rev(T) は S の接頭辞になっている。つまり図のオレンジ部分が等しくなっている。さらに青色の部分は回文になっているはずである。

f:id:pekempey:20170308182008p:plain

S の接頭辞であるような rev(Ti) をすべて見つけるには trie が使える。回文判定は manacher を使えばいいだろう。

重複して数えないように注意。