Problem Description

Given a string init, you need to support two operations:

• Append a string to the end of the current string.

• Query how many times a string $s$ appears in the current string (as a contiguous substring).

The operations are strictly online.

Input Format

The first line contains an integer $Q$, the number of operations.

The second line contains a string, the initial string init.

Next come $Q$ lines. Each line contains two strings, Type and Str.

• Type is ADD, meaning to append a string to the end.

• Type is QUERY, meaning to ask how many times a string appears in the current string.

To enforce online processing, you need to maintain a variable mask, initially $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);
}

After reading Str, use this process to decode it into the real string TrueStr.

For a query, query TrueStr and output one line with the answer Result.

Then update $mask = mask \bigoplus Result$.

For an insertion, append TrueStr to the end of the current string.

Note: the strings in both ADD and QUERY operations must be decoded.

Output Format

For each QUERY operation, output how many times the queried string appears in the current string.

2
A
QUERY B
ADD BBABBBBAAB

0

Hint

$|\mathrm{init}| \leq 6 \times 10^5$, $Q \leq 6 \times 10^5$, and the total length of all queried strings is at most $3 \times 10^6$.

It is guaranteed that the strings contain only A and B.

To avoid slow judging, for test points $2,3,5,6,8,11$ the time limit is 3 s, and for the others it is 1 s.

Original problem: BZOJ 2555.

Translated by ChatGPT 5