字符串

【题目描述】

令 $s$ 与 $w$ 为两字符串，下标从 $0$ 开始，定义：

   $w[l, r]$ 表示字符串 $w$ 在区间 $[l, r]$ 中的子串；

   $w$ 在 $s$ 中出现的频率定义为 $w$ 在 $s$ 中出现的次数；

   $f(s, w, l, r)$ 表示 $w[l, r]$ 在 $s$ 中出现的频率。

比如 $f(ababa, aba, 0, 2) = 2$ 。

现在给定串 $s$ ， $m$ 个区间 $[l, r]$ 和长度 $k$ ，你要回答 $q$ 个询问，每个询问给你一个长度为 $k$ 的字符串 $w$ 和两个整数 $a, b$ ，求：

$\sum\limits_{i = a} ^ b f(s, w, l_i, r_i)$

【输入格式】

第一行四个整数 $n, m, q, k$ ， $n$ 表示 $s$ 的长度。

接下来一行一个长为 $n$ 的字符串 $s$ 。

接下来 $m$ 行，每行两个整数表示 $l_i, r_i$ 。

接下来 $q$ 行，每行一个字符串 $w$ ，两个整数 $a, b$ 。

【输出格式】

对于每个询问一行，输出答案。

【样例1输入】

8 5 3 3
abacdaba
0 2
1 2
0 0
2 2
1 2
dab 1 4
bac 2 3
eeb 1 3

【样例1输出】

7
3
2

【样例2】

点击下载样例2

【数据规模与约定】

对于 $10\%$ 的数据， $n, m, k, q \leq 10$ ；

对于 $30\%$ 的数据，满足 $n, m, k, q \leq 10 ^ 2$ ；

对于 $50\%$ 的数据，满足 $n, m, k, q \leq 10 ^ 4$ ；

对于 $100\%$ 的数据，满足 $0 < n, m, k, q \leq 10 ^ 5, \sum |w| \leq 10 ^ 5, 0 \leq l_i, r_i < k, 0 \leq a, b < m$ ，字符串由小写英文字母构成。

【来源】

LOJ