CSAcademy #20 Palindromic Concatenation
https://csacademy.com/contest/round-20/#task/palindromic-concatenation
解法
文字列 S と文字列 T を結合して回文になる条件を考えてみよう。|S|>|T|のとき rev(T) は S の接頭辞になっている。つまり図のオレンジ部分が等しくなっている。さらに青色の部分は回文になっているはずである。
S の接頭辞であるような rev(Ti) をすべて見つけるには trie が使える。回文判定は manacher を使えばいいだろう。
重複して数えないように注意。