#6031. 「雅礼集训 2017 Day1」字符串

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

s w 为两字符串,定义:

  1. w[l, r] 表示字符串 w 在区间 [l, r] 中的子串;
  2. w s 中出现的频率定义为 w s 中出现的次数;
  3. f(s, w, l, r) 表示 w[l, r] s 中出现的频率。

比如 f(\texttt{ababa}, \texttt{aba}, 1, 3) = 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 的长度。
接下来一行一个长为 s 的字符串 s
接下来 m 行,每行两个整数表示 l_i, r_i
接下来 q 行,每行一个字符串 w ,两个整数 a, b

输出格式

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

样例

样例输入

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

样例输出

7
3
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\% 的数据,满足 n, m, k, q \leq 10 ^ 5, \sum w \leq 10 ^ 5 ,字符串由小写英文字母构成。