← 返回题目列表

Codeforces · 1098/F

F. F 函数

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

两个字符串 $$$s=s_1 s_2 \ldots s_n$$$ 和 $$$t = t_1 t_2 \ldots t_m$$$ 的最长公共前缀的长度定义为最大值 $$$k \le \min(n, m)$$$,使得 $$$s_1 s_2 \ldots s_k$$$ 等于$$$t_1 t_2 \ldots t_k$$$。我们将两个字符串 $$$s$$$ 和 $$$t$$$ 的最长公共前缀表示为 $$$lcp(s,t)$$$。

字符串 $$$s_1 s_2 \dots s_n$$$ 的 Z 函数是整数序列 $$$z_1, z_2, \ldots, z_n$$$,其中 $$$z_i = lcp(s_1 s_2 \ldots s_n,\ \ s_i s_{i+1} \dots s_n)$$$。字符串 $$$s$$$ 的 Ж 函数定义为 $$$z_1 + z_2 + \ldots + z_n$$$。

给你一个字符串 $$$s=s_1 s_2 \ldots s_n$$$ 和 $$$q$$$ 查询。每个查询由两个整数 $$$l_i$$$ 和 $$$r_i$$$ 描述,其中 $$$1 \le l_i \le r_i \le n$$$。查询的答案被定义为字符串 $$$s_{l_i} s_{l_i +1} \ldots s_{r_i}$$$ 的 Ж 函数。

输入

第一行包含字符串 $$$s$$$,由小写英文字母组成 ($$$1 \leq |s| \leq 200\,000$$$)。第二行包含一个整数 $$$q$$$ — 查询数量 ($$$1 \leq q \leq 200\,000$$$)。以下$$$q$$$ 行中的每一行都包含两个整数$$$l_i$$$ 和$$$r_i$$$,描述查询($$$1 \leq l_i \leq r_i \leq |s|$$$)。

输出

每个查询输出一个整数:对应子串的Ж函数值。

示例

输入 #1

abbd
4
2 3
1 3
3 3
1 4

输出 #1

3
3
1
4

输入 #2

bbaaa
5
2 4
1 5
1 5
3 3
1 2

输出 #2

3
6
6
1
3

注意

在第一个示例案例中,有四个查询:

- 第一个查询对应子字符串 bb,其 Ж 函数等于 $$$2 + 1 = 3$$$;
- 第二个查询对应子字符串 abb,其 Ж 函数等于 $$$3 + 0 + 0 = 3$$$;
- 第三个查询对应子字符串 b,其 Ж 函数等于 $$$1$$$。
- 第四个查询对应子字符串 abdd,其 Ж 函数等于 $$$4 + 0 + 0 + 0= 4$$$。