#P5408. [2018年湖南省队集训]string
[2018年湖南省队集训]string
[2018 年湖南省队集训] string
题目描述
给定 个字符串 ,它们都由数字字符组成。需要维护四种操作。
设 表示第 次操作结束后第 个字符串的内容, 为初始内容。出现次数统计的是子串的所有出现位置,允许相互重叠。
- 在当前第 个字符串的末尾追加一个数字字符。
- 查询历史字符串 在当前第 个字符串中出现了多少次。
- 查询当前 个字符串一共含有多少种不同的非空子串。内容相同的子串只算一种。
- 给定一个字符串 ,求 在任意一个当前字符串中的最大出现次数。
输入格式
第一行两个整数 。 表示强制在线, 表示直接使用输入。
接下来 行,每行一个初始字符串。
下一行一个整数 ,表示操作数。
接下来 行,每行按以下格式之一给出。
1 x y:在第 个字符串末尾追加一个字符。 时追加数字 。 时,追加的数字为 ,其中 为按位异或。2 x y z:查询 在当前第 个字符串中的出现次数。3:查询当前所有字符串中不同的非空子串个数。4 T:查询 在任意一个当前字符串中的最大出现次数。
初始为 ,随后取最近一次操作 或 的答案。操作 的答案不影响 。
输出格式
对每个操作 、 或 ,输出一行一个整数,表示答案。
样例
3 0
121
123
1
4
1 3 2
3
2 3 0 1
4 12
8
2
1
第一次查询时,不同的非空子串为 1、2、12、21、121、3、23、123,共 种。
第二次查询中,初始的第三个字符串 1 在 121 中出现两次。第三次查询中,12 在当前三个字符串中各出现一次,故最大次数为 。
数据范围
用 表示操作数 。 为初始字符串总长, 为操作 中各查询字符串的总长。
| 数据比例 | 限制 |
|---|---|
| ,,, | |
| 另外 | 不包含操作 |
| 另外 | |
| ,,, |