Substrings in a String

题意翻译

# 题目描述 给你一个字符串 $s$，共有 $q$ 次操作，每个都是下面两种形式的一种。 - `1 i c`：将字符串 $s$ 的第 $i$ 项变为字符 $c$。 - `2 l r y`：求字符串 $y$ 在字符串 $s$ 中以第 $l$ 项为起点，以第 $r$ 项为终点的子串（第 $l$ 和第 $r$ 项）中作为子串出现的次数。 $1\leq |s|\leq 10^5$，$1\leq q\leq 10^5$，$\sum |y| \leq 10^5$。

题目描述

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: - $ 1ic $ ( $ 1<=i<=|s| $ ) - $ 2lry $ ( $ 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 $ 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] $ .