#353. 2555. SubString

2555. SubString

SubString

题目描述

给定一个字符串 init,要求支持两个操作:

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

强制在线。

输入格式

第一行一个整数 QQ 表示操作个数。

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

接下来 QQ 行,每行 22 个字符串 Type,Str

  • TypeADD,表示在后面插入字符串。
  • TypeQUERY,表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作,你需要维护一个变量 mask,初始值为 00

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=maskResultmask=mask \bigoplus Result

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

注意:ADDQUERY 操作的字符串都需要解压。

输出格式

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

样例 #1

样例输入 #1

2
A
QUERY B
ADD BBABBBBAAB

样例输出 #1

0

提示

init6×105|\mathrm{init}| \leq 6 \times 10^5Q6×105Q \leq 6\times 10^5,询问总长度 3×106\leq 3 \times 10^6

保证字符串中只会出现 AB

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

原题:BZOJ 2555