SubString

题目描述

给定一个字符串 init，要求支持两个操作：

• 在当前字符串的后面插入一个字符串。
• 询问字符串 $s$ 在当前字符串中出现了几次。(作为连续子串)

强制在线。

输入格式

第一行一个整数 $Q$ 表示操作个数。

第二行一个字符串表示初始字符串 init。

接下来 $Q$ 行，每行 $2$ 个字符串 Type,Str。

• Type 是 ADD，表示在后面插入字符串。
• Type 是 QUERY，表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作，你需要维护一个变量 mask，初始值为 $0$。

String decodeWithMask(String s, int mask) {
	char[] chars = s.toCharArray();
	for (int j = 0; j < chars.length; j++) {
		mask = (mask * 131 + j) % chars.length;
		
		char t = chars[j];
		chars[j] = chars[mask];
		chars[mask] = t;
	}
	
	return new String(chars);
}

读入串 Str 之后，使用这个过程将之解码成真正询问的串 TrueStr。

询问的时候，对 TrueStr 询问后输出一行答案 Result。

然后 $mask=mask \bigoplus Result$。

插入的时候，将TrueStr插到当前字符串后面即可。

注意：ADD 和 QUERY 操作的字符串都需要解压。

输出格式

对于每一个 QUERY 操作，输出询问的字符串在当前字符串中出现了几次。

样例 #1

样例输入 #1

2
A
QUERY B
ADD BBABBBBAAB

样例输出 #1

0

提示

$|\mathrm{init}| \leq 6 \times 10^5$，$Q \leq 6\times 10^5$，询问总长度 $\leq 3 \times 10^6$。

保证字符串中只会出现 A 和 B。

为防止评测过慢，对于测试点 $2,3,5,6,8,11$ 时限为 3s，其余为 1s。

原题：BZOJ 2555