Substrings in a String
Contest: Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined)
Difficulty rating: 3000
Tags: bitmasks, brute force, data structures, string suffix structures, strings

Given a string s, process q queries, each having one of the following forms:

- 1 i c — Change the i-th character in the string to c.
- 2 l r y — Consider the substring of s starting at position l and ending at position r. Output the number of times y occurs as a substring in it.

Input format:
The first line of the input contains the string s (1 ≤ |s| ≤ 105) of lowercase English letters.

The second line contains an integer q (1 ≤ q ≤ 105)  — the number of queries to process.

The next q lines describe the queries and may have one of the following forms:

- 1 i c (1 ≤ i ≤ |s|)
- 2 l r y (1 ≤ l ≤ r ≤ |s|)

c is a lowercase English letter and y is a non-empty string consisting of only lowercase English letters.

The sum of |y| over all queries of second type is at most 105.

It is guaranteed that there is at least one query of second type.

All strings are 1-indexed.

|s| is the length of the string s.

Output format:
For each query of type 2, output the required answer in a separate line.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
Consider the first sample case. Initially, the string aba occurs 3 times in the range [1, 7]. Note that two occurrences may overlap.

After the update, the string becomes ababcbaba and now aba occurs only once in the range [1, 7].

Example input:
ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba

Example output:
3
1

Example input:
abcdcbc
5
2 1 7 bc
1 4 b
2 4 7 bc
1 2 a
2 1 4 aa

Example output:
2
2
1

Editorial:
Let N = |s|. Divide the given string into blocks of size $$K = \sqrt{N}$$ and use any suffix structure for each block. Complexity: O(|s|).
To update a character in the string, rebuild a suffix structure for that block. This takes O(K) per update.
We answer queries as follows. Remember that it’s given that the total length of all the query strings is at most 105.
If the size of the query string is greater than K, then the number of such strings will be at most y / K and hence we can directly use KMP in the string for the given range for all such strings. Overall Complexity: O(N * y / K)
If the size of the query string is less than K, we proceed as follows. For the occurrences of query string within a block, we can calculate them using the suffix structures for each block. This can be done in O(|y|) for each block, O(|y| * (N / k)) for the given range. For the occurrences that lie across two (adjacent) blocks, we only need to consider a string of 2 * |y|, we can simply use KMP for finding such occurrences. We need to choose the string carefully to avoid over counting (for more details, see the author’s solution). Its complexity will be O(N / k * 2 * |y|). For left and right blocks of the query range, we can again use KMP. The complexity would be O(2 * k). The overall complexity for the small query strings is therefore O(N / k * |y|). Hence, complexity over all such string would be O(y * N / k). Hence, the overall complexity is O(N * k + y * N / k). So choose any optimal K. Any K from 150 to 400 will fit in the time limit. Expected Complexity: O(N * sqrt(N))