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

28 人解决,307 人已尝试。

39 份提交通过,共有 854 份提交。

7.6 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年,9 月前.

最后提交: 4 周前.

来源: EOJ Monthly 2017.12

题目标签