公式解説では、ハッシュ値を用いた \(O(N \log^2 N)\) 時間の解法が紹介されていました。本解説では、Suffix Array, LCP Array および Cartesian Tree を利用した \(O(N)\) 時間の解法を紹介します。

こちらの解説 にも書いたとおり、答えは \(\displaystyle \max_{1 \leq i < j \leq N} \left\{ \min(\mathrm{LCP}(i, j), j - i) \right\}\) です。

\(S\) の Suffix Array を \(\mathrm{SA}\) とし、その逆順列を \(\mathrm{SA}^{-1}\) とします。また、\(S\) の LCP Array を \(\mathrm{LCPA}\) とします。\(\mathrm{LCP}(i, j)\) は、これらの配列を用いて書き表せます。具体的には、

\[\ell = \min(\mathrm{SA}^{-1}[i], \mathrm{SA}^{-1}[j]), r = \max(\mathrm{SA}^{-1}[i], \mathrm{SA}^{-1}[j])\]

とすると、

\[\mathrm{LCP}(i, j) = \min_{x \in [\ell, r)} \{\mathrm{LCPA}[x]\}\]

となります。さらにこのとき \(\{i, j\} = \{\mathrm{SA}[\ell], \mathrm{SA}[r]\}\) より \(j - i = |\mathrm{SA}[r] - \mathrm{SA}[\ell]|\) ですから、答えは

\[\max_{1 \leq \ell < r \leq N} \left\{ \min\left(\min_{x \in [\ell, r)} \{\mathrm{LCPA}[x]\}, |\mathrm{SA}[r] - \mathrm{SA}[\ell]|\right) \right\}\]

と書き表せます。

ここからは log をつけてよければさまざまな解法があると思います。たとえば答えで二分探索することで、\(O(N \log^2 N)\) 時間や \(O(N \log N)\) 時間の解法を得ることができます。

以下では、Cartesian Tree を利用した \(O(N)\) 時間の解法について説明します。

\(\mathrm{LCPA}\) をヒストグラムとみなし、その中の区間 \([\ell, r)\)、高さ \(h\) の長方形を選んで \(\displaystyle \min(h, |\mathrm{SA}[r] - \mathrm{SA}[\ell]|)\) を最大化する問題と考えます。長方形を選ぶ際、

• 先に区間 \([L, R)\)、高さ \(\displaystyle H = \min_{x \in [L, R)} \{\mathrm{LCPA}[x]\}\) の極大な長方形を選んでから、そこに含まれる区間 \([\ell, r)\)、高さ \(h = H\) の長方形を選ぶ

と考えることにします。\([L, R)\) を固定すると、\(\ell, r\) は \(\mathrm{SA}[\cdot]\) を最大化・最小化するものを選ぶのが最適です。

よって、極大な長方形の区間 \([L, R)\) それぞれに対し、\([L, R]\) での \(\mathrm{SA}\) の最大値・最小値を求めればよいです。\(i\) 番目の要素から左右を見る形の極大な長方形は、Cartesian Tree の頂点 \(i\) の子孫がなす区間に対応していることに注目すると、Cartesian Tree 上で木 DP を行うことで解けます。

実装例