该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
题目背景
日记非常喜欢用记事本写代码。但是,由于记事本的性能优化很差,她的电脑经常卡死。所以她希望实现一个负载计算器来分析电脑为什么会卡死。
题目描述
日记使用的编程语言是 Neko Lang,这是一种只使用小写字母的编程语言。语言中有一个模式串 P=P1…P∣P∣。设她当前的字符串为 S=S1…S∣S∣,她只进行五种操作:
操作的参数中,除 s,c 外均为非负整数,而 s 为只包含小写字母的字符串,c 为小写字母。
Insert p s
在第 p 个字符后插入字符串 s,使 S←S1…Sps1…s∣s∣Sp+1…S∣S∣。若 p=0 则为在字符串开头插入。
Delete l r
删除第 l 到第 r 个字符,使 S←S1…Sl−1Sr+1…S∣S∣。
Replace l r s
将第 l 到第 r 个字符替换为字符串 s,使 S←S1…Sl−1s1…s∣s∣Sr+1…S∣S∣。
Count l r c
输出第 l 到第 r 个字符间字母 c 的个数,即 i=l∑r[Si=c]。
Search l r
输出第 l 到第 r 个字符间模式串 P 的出现次数,即 i=l∑r−∣P∣+1j=1min∣P∣[Si+j−1=Pj]。
日记认定,是她使用了太多次查询操作,使得电脑卡死了。所以,你需要帮助日记计算出两种查询操作的结果,这样日记就可以确认自己的想法了。
输入格式
第 1 行,1 个正整数 n 和 1 个字符串 P,其中 n 为操作次数。
接下来 n 行,每行按上述格式描述一次操作。
输出格式
每次查询操作 1 行,为对应操作的结果。
数据范围
本题设置 25 个测试点,每个测试点 4 分。同时,记五种操作的次数依次为 a1…a5,每个测试点满足一些限制,见下:
测试点编号 |
n≤ |
ai |
1 |
10 |
a5=0 |
2 |
|
3 |
100 |
a2=a3=a5=0 |
4 |
a5=0 |
5 |
|
6 |
103 |
a2=a3=a5=0 |
7 |
a3=a5=0 |
8 |
a5=0 |
9 |
|
10 |
11 |
104 |
a2=a3=a5=0 |
12 |
a3=a5=0 |
13 |
a5=0 |
14 |
|
15 |
16 |
105 |
a2=a3=a5=0 |
17 |
a3=a5=0 |
18 |
19 |
a5=0 |
20 |
21 |
a5≤10 |
22 |
a5≤100 |
23 |
|
24 |
25 |
对全部数据,保证 1≤n≤105,∣s∣≤105,∑∣s∣≤10n,∣P∣≤20。
输入样例 1
8 abababc
Insert 0 abababababababab
Search 1 16
Count 1 16 a
Replace 7 8 cabc
Search 1 18
Count 1 18 c
Insert 7 abab
Search 1 14
输出样例 1
0
8
1
2
2
输入样例 2
2 ababab
Insert 0 abababababababab
Search 1 16
输出样例 2
6
样例解释
样例解释 1
每个操作结束后,字符串依次为:
abababababababab
abababababababab
abababababababab
abababcabcabababab
abababcabcabababab
abababcabcabababab
abababcabababcabababab
abababcabababcabababab
样例解释 2
注意,两个匹配的范围可以重叠。如果你不理解这句话的含义,请仔细阅读题目描述中匹配的形式化定义。