[AdditionalFile5373.zip](file://AdditionalFile5373.zip?type=additional_file)

#5373. 「OOI 2023 Day 2」子串小问题

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2023 Day2 T1 「Задачечка на подстрочечки」。

菲利普非常喜欢解决与字符串相关的问题。他已经解决了所有他知道的字符串问题，但仍觉得不够。于是，菲利普决定自己设计一个新的字符串问题。

为此，他选取了一个字符串 $t$ 和一个包含 $n$ 个字符串的集合 $s_1, s_2, s_3, \ldots, s_n$。菲利普有 $m$ 个查询，在第 $i$ 个查询中，他希望从字符串 $t$ 中提取从第 $l_i$ 个到第 $r_i$ 个字符的子串，并计算其中与集合中某个字符串相同的子串数量。更正式地说，菲利普希望计算满足 $l_i \le a \le b \le r_i$ 的位置对 $(a, b)$ 数量，其中 $t$ 从第 $a$ 个到第 $b$ 个字符的子串与集合中的某个字符串 $s_j$ 完全一致。

字符串 $t$ 从第 $a$ 个到第 $b$ 个字符的子串是指通过删除 $t$ 的前 $a-1$ 个字符和后 $|t|-b$ 个字符得到的字符串，其中 $|t|$ 表示字符串 $t$ 的长度。

菲利普已经解决了这个问题，你能解决吗？

输入格式

第一行包含两个正整数 $n$ 和 $m$ $(1 \le n, m \le 500000)$，分别表示集合中的字符串数量和查询数量。

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

接下来的 $n$ 行描述集合中的字符串。第 $i$ 行包含一个字符串 $s_i$，由小写英文字母组成。设 $S$ 为集合中所有字符串的总长度。保证 $S \le 10^{6}$，且所有字符串 $s_i$ 互不相同。

接下来的 $m$ 行描述查询。第 $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

输出

7 3 5 3 1

在第一个样例中，第一个查询要求对整个字符串计算与集合中字符串相同的子串数量。与字符串 aba 匹配的子串有 $[1, 3]$ 和 $[4, 6]$；与字符串 a 匹配的子串有 $[1, 1]$、$[3, 3]$、$[5, 5]$、$[7, 7]$；与字符串 ac 匹配的子串有 $[3, 4]$。因此，字符串 abacaba 中共有 $7$ 个子串与集合中的字符串匹配。

在第二个查询中，从原始字符串中提取位置 $1$ 到 $3$ 的子串，即 aba。其中，字符串 aba 出现 $1$ 次，字符串 a 出现 $2$ 次，字符串 ac 没有作为子串出现。

在第三个查询中，从原始字符串中提取位置 $2$ 到 $7$ 的子串，即 bacaba。其中，字符串 aba 出现 $1$ 次，字符串 a 出现 $3$ 次，字符串 ac 出现 $1$ 次作为子串。

样例 2

输入

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

输出

2 0 2 3

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。