← 返回题目列表

AtCoder · pakencamp_2021_day2_o

O. 高尔夫

中文机器翻译题面 查看原题

配点 : 600 点

問題文

文字列 S 。 将 S[i:j] 由于无法替换 S 的 i 从第一个字符开始 j 让我们表示提取到第一个字符的字符串。 当

文字列 T 满足以下所有条件时, T 是 它仅由好字符串。

  • 1 \leq |T| \leq |S|
  • S[i:i+|T|-1] = T 的整数 i 只是 1 仅存在一个

例如 当 S 是 在 abcbabc 时, cb 呀 abcb 、 abcbabc 是 它仅由好字符串但是, 不是 abc 呀 zyx 是 它仅由好字符串。 您将收到

Q 查询,因此请处理它们。 在第 i 个查询中 给定 1 \leq L_i \leq R_i \leq |S| 的整数 L_i, R_i ,打印以下问题的答案。

  • 2 整数 l, r 和 判断是否存在满足 1 \leq l \leq L_i 和 R_i \leq r \leq |S| 和 考虑类似 S[l:r] 是 在好字符串的东西。 r-l+1 的最小值是多少?

制約

  • S 由小写字母组成 打印第
  • 1 \leq |S| \leq 2 \cdot 10^5
  • 1 \leq Q \leq 2 \cdot 10^5
  • 1 \leq L_i \leq R_i \leq |S| \, (1 \leq i \leq Q)

入力

输入将以以下形式从标准输入给出。

S
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

Q 行。 输出 i \, (1 \leq i \leq Q) 在线 i 个查询的答案。 在第


入力例 1

abcbabc
5
2 3
2 5
1 7
4 4
6 6

出力例 1

3
4
7
2
3

1 个查询中, l=2, r=4 然后 r-l+1=3 ,这是最小值。 bc 是 它仅由好字符串,所以 不允许 l=2, r=3 。

2 个查询中, l=2, r=5 然后 r-l+1=4 ,这是最小值。

3 个查询中, l=1, r=7 然后 r-l+1=7 ,这是最小值。一般来说 S 事情是 请注意好字符串。


入力例 2

yyxxzzyyxx
5
3 3
1 1
10 10
5 5
7 7

出力例 2

3
5
5
2
2

入力例 3

qprrrrrpprqrrppq
20
7 8
6 8
4 7
7 12
6 7
5 5
6 8
4 6
4 4
2 3
7 11
8 9
6 7
11 12
11 15
5 6
4 5
13 13
9 13
5 7

出力例 3

4
4
5
6
4
4
4
5
3
3
5
3
4
2
5
4
4
3
5
4

原案: 森林