ABC284 F - ABCBAC - かんプリンの学習記録

問題概要

長さ ${2N}$ の文字列 ${T}$ が与えられる．長さ ${N}$ の文字列 ${S}$ であって， ${T=S[0,i)+rev(S)+S[i,N)}$ となるようなものを求めよ．

${T[i,j)}$ で文字列 ${T}$ の ${i}$ 文字目から ${j-1}$ 文字目までの文字列とします．
${rev(T)}$ で文字列 ${T}$ を反転させた文字列とします．

すべての ${i}$ で以下の判定が高速に行えればこの問題を解くことができます．

例として以下の入力を考えます．

以下のような判定ができればよいです．

必要な操作は

となりますが，これはローリングハッシュを用いることで前処理 ${O(N)}$ のもと，すべて ${O(1)}$ で行うことができます．

ロリハやるだけでした