30 人解决，321 人已尝试。
41 份提交通过，共有 902 份提交。
7.6 EMB 奖励。
3442. 唐纳德与子串 (Hard)
单点时限: 2.5 sec
内存限制: 512 MB
子串的定义是在一个字符串中连续出现的一段字符。这里，我们使用 $s[l \ldots r]$ 来表示 $s$ 字符串从 $l$ 到 $r$（闭区间）的子串。在本题中，字符串下标从 $0$ 开始。显然，对于长度为 $n$ 的字符串共有 $\frac{n(n+1)}{2}$ 个子串。
对于一个给定的字符串 $s$，唐纳德给出 $q$ 次询问，第 $i$ 次询问包括三个参数 $l_i, r_i, z_i$，问在 $s[l_i \ldots r_i]$ 的所有子串中共有多少个恰好为 $z_i$。
输入格式
输入具有如下形式：
$s \
q \
l_1 \ r_1 \ z_1 \
l_2 \ r_2 \ z_2 \
\vdots \
l_q \ r_q \ z_q$
第一行一个字符串 $s$。
第二行一个整数 $q$。
接下来每行：首先两个整数 $l_i, r_i$ ($0 \le l_i \le r_i < |s|$)，然后是一个非空字符串 $z_i$。整数和整数，整数和字符串间以单空格隔开。
字符串中只会出现 $26$ 个小写英文字母。
数据规模约定：
- 对于 Easy 档：$1 \le |s| \le 100, q \le \sum |z_i| \le 100$。
- 对于 Hard 档：$1 \le |s| \le 10^5, q \le \sum |z_i| \le 10^5$。
输出格式
对于每次询问，输出一个整数，表示答案。
样例
Input
thisisagarbagecompetitionhahahah 5 0 30 a 1 5 is 25 30 hah 6 12 ag 7 12 ag
Output
6 2 2 2 1
题目标签