\(B_i \coloneqq \min(\lbrace j \mid S[i:j] \text{は良い文字列} \rbrace)\) とします。ただしそのような \(j\) が存在しない場合は \(B_i \coloneqq |S|\) とします。 \(B_1, B_2, \ldots, B_{|S|}\) の値は LCP 配列を用いて \(O(|S|)\) 時間で計算できます。

\(i\) 番目のクエリで求めたいものは次の値です。

\[ \min_{1 \leq j \leq L_i}　\max(B_j, R_i - j + 1) \]

各 \(j\) について、 \(R\) を大きくしていったときの \(\max(B_j, R - j + 1)\) の挙動は次のようになります。

• \(R < B_j + j\) のとき \(\max(B_j, R - j + 1) = B_j\)
• \(R \geq B_j + j\) のとき \(\max(B_j, R - j + 1) = R - j + 1\)

クエリを先読みして \(R_i\) の昇順でソートしておきます。 \(R\) を大きくしながら各 \(j\) について現在 \(R < B_j + j\) なのかどうかを管理することで、一点更新区間最小値を処理するセグメント木でクエリに答えることができます。計算量は \(O(N + Q \log Q + Q \log N)\) です。