← 返回题目列表

Codeforces · 914/F

F. 字符串中的子字符串

中文机器翻译题面 查看原题

给定一个字符串 s,处理 q 个查询,每个查询具有以下形式之一:

- 1 i c — 将字符串中的第 i 个字符更改为 c。
- 2 l r y — 考虑 s 的子字符串,从位置 l 开始,到位置 r 结束。输出 y 作为子字符串在其中出现的次数。

输入

输入的第一行包含小写英文字母的字符串 s (1 ≤ |s| ≤ 105)。

第二行包含一个整数 q (1 ≤ q ≤ 105) — 要处理的查询数。

接下来的 q 行描述查询,可能具有以下形式之一:

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

c 为小写英文字母,y 为仅由小写英文字母组成的非空字符串。

|y| 的总和所有第二类型的查询最多为 105。

保证至少有一个第二类型的查询。

所有字符串的索引都是 1。

|s|是字符串 s 的长度。

输出

对于类型 2 的每个查询,在单独的行中输出所需的答案。

示例

输入 #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

注意

考虑第一个示例案例。最初,字符串 aba 在 [1, 7] 范围内出现 3 次。请注意,两次出现可能会重叠。

更新后,字符串变为 ababcbaba,现在 aba 在 [1, 7] 范围内仅出现一次。