ydc 很喜欢字符串,他有特别的视角看待字符串。
字符串是由字符组成的。字符一共
对于整数
ydc 将给你
- 操作0:在第
个字符串后面加上一个字符 。保证 , 。 - 操作1:询问当前第
个字符串中有多少个子串满足在第 个操作过后的第 个字符串能通过 与该子串相等。 是小于当前操作编号的非负整数, 表示在所有操作之前。保证 , 。 - 操作2:将第
个字符串改成第 个字符串。保证 。 - 操作3:给你一个字符串
,对于这 个串中的每个串询问有多少个子串满足 能通过 与该子串相等, 。
另外,输入文件可能被加密来强制你在线进行操作。
输入格式
第一行三个整数数,
如果数据被加密,令
字符串将按照如下格式给出:第一个数为一个正整数
接下来
再读入一个正整数
接着
如果是操作0,那么接着两个整数
如果是操作1,那么接着五个整数
如果是操作2,那么接着两个整数
如果是操作3,那么接着两个整数
输出格式
按照输入顺序回答询问。
对于每个操作1,输出一行一个整数表示答案。
对于每个操作3,输出一行
样例一
input
3 3 0 5 0 1 1 1 2 1 1 2 1 1 4 0 1 1 3 0 1 1 1 2 2 1 1 1 2 0 0 1
output
3 0 1 3
样例二
input
3 3 1 5 0 1 1 1 2 1 1 2 1 1 4 0 1 1 3 0 1 1 1 3 3 0 0 0 3 1 1 0
output
3 0 1 3
限制与约定
初始
操作3中读入的串总长度不超过
保证数据合法。
保证存在一个长度不超过
对于前 30% 的数据,保证
对于前 60% 的数据,保证所有的
对于前 80% 的数据,保证数据没有被加密。
时间限制:
空间限制:
来源
中国国家集训队互测2015 - By 刘研绎