Repeat String Query

2 secs 1024 MB
bayashiko's icon bayashiko

問題文

文字列 SS が与えられるので、QQ 個のクエリに答えてください。ii 個目のクエリは以下の通りです。

  • SSlil_i 文字目から rir_i 文字目までの連続部分文字列を SS' とする。次の条件を満たす正整数 kk の最大値を求めよ。

  条件 :: ある文字列 TT が存在し、 TTkk 個繋げたものが SS' と等しい。

  

制約

  • 1S30001\leq |S| \leq 3000
  • 1Q5000001\leq Q \leq 500000
  • 1liriS1\leq l_i \leq r_i \leq |S|
  • SS は英小文字からなる
  • Q,li,riQ,l_i,r_i は整数   

入力

入力は以下の形式で標準入力から与えられます。

SS
QQ
l1 r1l_1 \ r_1
l2 r2l_2 \ r_2
::
lQ rQl_Q \ r_Q

  

出力

答えを QQ 行出力してください。 ii 行目には、 ii 番目のクエリに対する答えを出力してください。

  

入力例1

ababcdfababcdfxxxx
4
2 4
1 4
1 14
15 18

出力例1

1
2
2
4

"bab" に対する答えは 11 です。
"abab""ab"22 個繋げたものなので、"abab" に対する答えは 22 です。
"ababcdfababcdf""ababcdf"22 個繋げたものなので、"ababcdfababcdf" に対する答えは 22 です。
"xxxx""x"44 個繋げたものなので、"xxxx" に対する答えは 44 です。"xx"22 個繋げたものでもありますが、条件を満たす kk のうち最大値を答えることに注意してください。

提出


Go (1.21)