CF914F.Substrings in a String

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

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

$1ic$ — Change the $i$ -th character in the string to $c$ .
$2lry$ — 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.

The first line of the input contains the string $s$ ( $1<=|s|<=10^{5}$ ) of lowercase English letters.

The second line contains an integer $q$ ( $1<=q<=10^{5}$ ) — the number of queries to process.

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

$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 $10^{5}$ .

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$ .

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

输入#1

ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba

输出#1

3
1

输入#2

abcdcbc
5
2 1 7 bc
1 4 b
2 4 7 bc
1 2 a
2 1 4 aa

输出#2

2
2
1

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]$ .