题目描述
给定字符串 s、m 个区间 [li,ri] 和整数 k。记 w[l,r] 为字符串 w 的下标区间 [l,r] 对应的子串,字符串下标从 0 开始。记 f(s,w,l,r) 为 w[l,r] 在 s 中出现的次数。
每个询问给定长度为 k 的字符串 w 和两个整数 a,b,求
i=a∑bf(s,w,li,ri).
区间编号也从 0 开始。例如,若 s=ababa,w=aba,则 f(s,w,0,2)=2。
输入格式
第一行四个整数 n,m,q,k,其中 n 是 s 的长度,q 是询问数。
第二行一个长度为 n 的字符串 s。
接下来 m 行,每行两个整数 li,ri。之后 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≤10。
- 对于 30% 的数据,n,m,k,q≤102。
- 原题对 50% 和所有数据均列出 n,m,k,q≤104。
- 对于所有数据,询问字符串的总长度不超过 105,字符串均由小写英文字母组成。
原 PDF 题面