#P6788. [2019福建夏令营]大水题
[2019福建夏令营]大水题
大水题
题目描述
给定 个模式串 ,以及一个字符串 。所有字符串均由小写英文字母组成。
依次执行 次操作,分为以下两种:
1 l r str:把 的区间 覆盖为str不断重复后的前 个字符。每次重复都从本次修改的左端点 开始对齐, 的总长度不变。例如,长度为 的区间用abc修改后变成abcabca。2 l r:求所有模式串在当前子串 中出现的总次数。
每次修改都会影响之后的操作。查询只统计完全位于 中的匹配,允许不同匹配重叠;每个模式串、每个起始位置分别计数。若两个模式串内容相同,它们作为不同的 分别贡献次数。
输入格式
第一行两个整数 ,分别表示模式串个数和操作数。
接下来 行,每行一个非空字符串 ,长度不超过 。保证把全部 插入一棵字典树后,字典树的大小不超过 。
接下来一行一个非空字符串 ,长度不超过 。
接下来 行,每行描述一个操作,格式如上。其中 ,修改串 str 非空。
输出格式
每个类型为 的操作输出一行一个整数,表示对应查询的总出现次数。
样例输入
2 5
aa
aba
aabaab
2 1 6
1 3 5 b
2 2 3
1 1 6 a
2 1 5
样例输出
3
0
4
数据范围与子任务
所有数据满足 ,,,所有修改操作中 str 的长度总和不超过 。所有字符串仅由小写英文字母组成。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | ,, | |
| 2 | ,, | |
| 3 | ,, | |
| 4 | ,, | |
| 5 | 无 |