CF914F Substrings in a String

给定一个字符串 $s$，以及 $q$ 个查询，每个查询的格式如下： - $1~i~c$ —— 将字符串中第 $i$ 个字符修改为 $c$。 - $2~l~r~y$ —— 取 $s$ 的子串，区间为 $[l, r]$，并输出 $y$ 作为子串在其中出现的次数。

第一行输入一个仅由小写英文字母组成的字符串 $s$，其中 $1 \leq |s| \leq 10^{5}$。 第二行输入一个整数 $q$，表示需要处理的查询数，$1 \leq q \leq 10^{5}$。 接下来的 $q$ 行，每行描述一个查询，格式如下： - $1~i~c$，$1 \leq i \leq |s|$； - $2~l~r~y$，$1 \leq l \leq r \leq |s|$。 其中 $c$ 为小写英文字母，$y$ 为非空小写英文字母字符串。 所有 2 型查询中，$\sum |y| \leq 10^{5}$。 保证至少存在一个 2 型查询。 所有字符串均采用 1 下标。 $|s|$ 表示字符串 $s$ 的长度。

对于每个类型为 $2$ 的查询，输出要求的答案，每个答案单独占一行。

以第一个样例为例。初始时，字符串 aba 在区间 $[1,7]$ 内出现了 $3$ 次。注意两次出现可能重叠。 更新后，字符串变为 ababcbaba，此时在区间 $[1,7]$ 内 aba 仅出现 1 次。 由 ChatGPT 5 翻译