解説放送を見て道筋は理解できたが、そこからが長かった。 比較的実装が重い問題だと思う。
答えの回文LRを文字列Lと文字列Rに分けて考える。どちらも空文字列で初期化しておく。
$s_i$を追加するときは、Lの右側に追加するか、あるいはRの左側に追加する。
何度か$s_i$を追加して、L="abcde"、R="cba" となったとする。
このとき部分文字列 abc はすでに回文の条件を満たすのでL="abc"、R=""と見なしてもよいということになる。
なので、LとRの組 (L, R) を頂点として、ダイクストラ法を適用していけばよい。
LやRとして現れるのは$s_i$のPrefixとSuffixのみなので、今回の制約では十分間に合う。
頂点 (L, R) からの遷移については、すべての$s_i$について、$s_i$をLあるいはRに追加したときに部分的に回文の条件を満たすかどうかをチェックする。条件を満たす場合には、次の頂点に遷移できる。