A6685 | $「雅礼集训 2017 Day1」字符串$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

令 $ s $ 与 $ w $ 为两字符串，**下标从 $0$ 开始**，定义： 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}, 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

C++ 编辑器

输入

输出