実は、答えが Infinite であるための必要十分条件は、\(X\) に含まれる ( と ) の個数が等しいことです。

\(X\) に含まれる ( と ) の個数が異なるとき、答えが Finite であることを示します。

\(Y\) は次のいずれかの形で書けます。

• \(X\) のある部分文字列
• 次の \(3\) つの文字列をこの順に連結した文字列
  • \(X\) のある接尾辞（空でもよい）
  • ある非負整数 \(k\) が存在して、\(X\) を \(k\) 回連結した文字列
  • \(X\) のある接頭辞（空でもよい）

前者の長さは明らかに有限です。後者について、\(k\) を十分大きくとると、この文字列に含まれる ( と ) の個数は等しくなりえず、ゆえに正しい括弧列ともなりえないことがわかります。よって、答えは Finite です。

\(X\) に含まれる ( と ) の個数が等しいとき、答えが Infinite であることを示します。

有名事実として、\(X\) を巡回シフトした文字列であって正しい括弧列である文字列 \(Z\) が存在します。実際、次のように \(Z\) を構成できます。

• \(A_i\) を \((X[1, i]\) に含まれる( の個数\()-(X[1, i]\) に含まれる ) の個数\()\) とする。
  • ここで、\(X[l, r]\) は \(X\) の \(l\) 文字目から \(r\) 文字目までからなる部分文字列を表す。
• \(A_i\) が最小となる \(i\) に対し、\(X[i+1, |X|] + X[1, i]\) を \(Z\) とする。
  • ここで、\(|X|\) は \(X\) の長さを表す。また、\(+\) は文字列の連結を表す。

このように構成した \(Z\) の任意の接頭辞について、\((\)( の個数\()-(\)) の個数\()\) が非負であることが確認できます。

任意の正整数 \(k\) に対し、\(Z\) を \(k\) 回連結した文字列は \(Y\) として選ぶことができます。よって、答えは Infinite です。

以上で必要十分条件が証明できました。

したがって、累積和を用いて \(O(N + Q)\) 時間で解くことができます。