比赛场次 564
比赛名称 4043级2023省选练习赛4
比赛状态 已结束比赛成绩
开始时间 2023-03-10 18:00:00
结束时间 2023-03-10 22:00:00
开放分组 全部用户
注释介绍 周末愉快
题目名称 字符串
输入输出 sumstring.in/out
时间限制 3000 ms (3 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分

字符串

★★★☆   输入文件:sumstring.in   输出文件:sumstring.out   简单对比
时间限制:3 s   内存限制:256 MiB

【题目描述】

令 $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