3441. 唐纳德与子串 (Easy)

单点时限: 1.0 sec

内存限制: 256 MB

子串的定义是在一个字符串中连续出现的一段字符。这里,我们使用 来表示 字符串从 (闭区间)的子串。在本题中,字符串下标从 开始。显然,对于长度为 的字符串共有 个子串。

对于一个给定的字符串 ,唐纳德给出 次询问,第 次询问包括三个参数 ,问在 的所有子串中共有多少个恰好为

输入格式

输入具有如下形式:

第一行一个字符串

第二行一个整数

接下来每行:首先两个整数 (),然后是一个非空字符串 。整数和整数,整数和字符串间以单空格隔开。

字符串中只会出现 个小写英文字母。

数据规模约定:

  • 对于 Easy 档:
  • 对于 Hard 档:

输出格式

对于每次询问,输出一个整数,表示答案。

样例

Input
thisisagarbagecompetitionhahaha
5
0 30 a
1 5 is
25 30 hah
6 12 ag
7 12 ag
Output
6
2
2
2
1

762 人解决,935 人已尝试。

853 份提交通过,共有 2774 份提交。

1.6 EMB 奖励。

创建: 1 年,11 月前.

修改: 1 年,11 月前.

最后提交: 1 月,2 周前.

来源: EOJ Monthly 2017.12

题目标签