[AtCoder] 第二回全国統一プログラミング王決定戦本戦 B – NIKKEI String

問題

方針

\( n = |S| \) とします。\( S_3 , \ S_4 \) を固定して考えます。\( S \) の \( i \) 文字目から \( j \) 文字目までの部分文字列を \( S(i, j) \) \( (0 \leq i \leq j \leq n – 1)\)とします。このとき、

\begin{eqnarray}
S_3 &=& S(i, j)\\
S_4 &=& S(i + j + 1, i + 2j + 1)
\end{eqnarray}

と表現できます。また、制約は、\( 1 \leq i \leq n – 4 \wedge 0 \leq i + 2j +1\leq n – 3 \) です。次に、\( S_2, \ S_6 \) について探索を行います。これは、\( S_2, \ S_6 \) の末尾から先頭に向かって走査していくことで実現可能です。尺取り法のように文字列を伸ばしていく感じだと思います。

コード