疯狂的串串¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
一支小队完成几何练习的任务后，在一家烤串店用餐。餐桌上各色食材排成一串，让他们想起新收到的字符串查询订单：需要在一段串中找出指定模式出现了几次。
形式化问题描述¶
给定仅含小写英文字母的字符串 \(S\) ，位置从 \(1\) 到 \(|S|\) 编号。每次查询给定整数 \(l,r\) 和非空字符串 \(t\) ，统计 \(t\) 在子串 \(S_lS_{l+1}\cdots S_r\) 中的出现次数。
一次出现必须完整位于 \([l,r]\) 内。起始位置不同就算不同的一次出现，允许两次出现部分重叠。若模式串比查询区间长，答案为零。
在整个串 aaababa 中，aba 出现在 \([3,5]\) 和 \([5,7]\) ，共两次。
输入格式¶
第一行字符串 \(S\) . 第二行整数 \(M\) ，表示查询数。接下来 \(M\) 行，每行两个整数 \(l,r\) 和一个字符串 \(t\) ，以空格分隔。
输出格式¶
输出 \(M\) 行，每行一个整数，表示对应查询的出现次数。
样例¶
样例 1¶
输入¶
aaababa
6
1 2 aa
1 7 aba
3 6 aba
4 7 aba
1 3 aa
1 7 c
输出¶
1
2
1
1
2
0
样例 2¶
输入¶
aaaaa
5
1 5 aaa
2 4 aaaa
1 5 a
2 4 aa
1 1 aa
输出¶
3
0
5
2
0
样例 3¶
输入¶
abcdef
3
1 6 xyz
1 3 abc
2 6 abc
输出¶
0
1
0
样例解释¶
样例 1 中，查询 \([3,6]\) 时只有从位置 \(3\) 开始的 aba 完整位于区间中；从位置 \(5\) 开始的那次超出了右端点。
样例 2 的 aaa 在 aaaaa 中有三次重叠出现；在长度为三的区间中查找 aaaa 则得到零。
数据范围与保证¶
对 100% 的数据：\(1\le l\le r\le |S|\le1000\) ，\(1\le M\le1000\) ，\(1\le|t|\le40\) . \(S\) 与所有 \(t\) 都只含小写英文字母。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |