← 返回题目列表

Codeforces · 1801/G

G. 子字符串任务

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

为此,他采用了字符串 $$$t$$$ 和一组 $$$n$$$ 字符串 $$$s_1$$$、$$$s_2$$$、$$$s_3$$$、...、$$$s_n$$$。 Philip 有 $$$m$$$ 个查询,在第 $$$i$$$ 个查询中,Philip 希望获取字符串 $$$t$$$ 中从第 $$$l_i$$$ 到第 $$$r_i$$$ 个字符的子字符串,并计算与集合中某个字符串匹配的子字符串的数量。更正式地说,Philip 想要计算位置对 $$$a$$$、$$$b$$$ 的数量,使得 $$$l_i \le a \le b \le r_i$$$,并且字符串 $$$t$$$ 从第 $$$a$$$ 到第 $$$b$$$ 字符的子字符串与集合中的某个字符串 $$$s_j$$$ 一致。

字符串$$$t$$$从第$$$a$$$到第$$$b$$$字符的子字符串是从$$$t$$$中删除开头的$$$a - 1$$$字符和$$$|t|得到的字符串。 - 从末尾开始 b$$$ 个字符,其中 $$$|t|$$$ 表示字符串 $$$t$$$ 的长度。

菲利普已经解决了这个问题,但是你能吗?

输入

第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 500\,000$$$) - 集合中的行数和查询数。

第二行包含单个字符串 $$$t$$$,由英文字母的小写字母组成 ($$$1 \le |t| \le 5 \cdot 10^6$$$)。

以下 $$$n$$$ 行描述了该集合中的字符串。在其中的第 $$$i$$$ 中,给出单个字符串 $$$s_i$$$,由英文字母的小写字母组成。用 $$$S$$$ 表示集合中所有字符串的总长度。保证$$$S \le 10^6$$$,并且$$$s_i$$$的所有字符串都不同。

在以下行中,输入查询。其中第 $$$i$$$ 包含两个正整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le |t|$$$) - 来自第 $$$i$$$ 查询的子字符串 $$$t$$$ 的左边界和右边界。

输出

在一行中,打印 $$$m$$$ 个整数,其中第 $$$i$$$ 个整数应等于第 $$$i$$$ 个查询的答案。

示例

输入 #1

3 5
abacaba
aba
a
ac
1 7
1 3
2 7
2 5
4 5

输出 #1

7 3 5 3 1

输入 #2

4 4
abcdca
ab
ca
bcd
openolympiad
1 5
2 2
2 6
1 6

输出 #2

2 0 2 3

注意

在第一个示例中,第一个查询需要整个字符串来计算集合中包含的子字符串的数量。子字符串 $$$[1, 3]$$$ 和 $$$[4, 6]$$$ 与字符串“aba”一致。子字符串与字符串“a”$$$[1, 1]$$$、$$$[3, 3]$$$、$$$[5, 5]$$$、$$$[7, 7]$$$ 匹配。子字符串 $$$[3, 4]$$$ 与字符串“ac”匹配。总共,字符串“abacaba”的 7 个子字符串与集合中的字符串匹配。

在第二个查询中,从源字符串中取出位置1到位置3的子字符串,即字符串“aba”。字符串“aba”进入其中 1 次,字符串“a”进入其中 2 次,字符串“ac”作为子字符串不进入其中一次。 在第三个查询中,从源字符串中取出第2个到第7个位置的子字符串,这就是字符串“bacaba”。作为子串,字符串“aba”被包含在其中1次,字符串“a”被包含3次,字符串“ac”被包含1次。