F. Substrings in a String

Codeforces

IDCF914F

Time6000ms

Memory256MB

Difficulty—

bitmasksbrute forcedata structuresstring suffix structuresstrings

English · Original

Chinese · Translation

Formal · Original

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 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 For each query of type 2, output the required answer in a separate line. [samples] ## 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\].

给定一个字符串 $s$，处理 $q$ 个查询，每个查询具有以下形式之一：输入的第一行包含字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。第二行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——需要处理的查询数量。接下来的 $q$ 行描述查询，可能具有以下形式之一： $1\ i\ c$（$1 ≤ i ≤ |s|$） $2\ l\ r\ y$（$1 ≤ l ≤ r ≤ |s|$）其中 $c$ 是一个小写英文字母，$y$ 是一个仅由小写英文字母组成的非空字符串。所有第二类查询中 $|y|$ 的总和不超过 $10^5$。保证至少存在一个第二类查询。所有字符串均为 $1$-索引。 $|s|$ 表示字符串 $s$ 的长度。对于每个第二类查询，请在单独一行中输出所需答案。考虑第一个样例。初始时，字符串 _aba_ 在区间 $[1, 7]$ 中出现 $3$ 次。注意，两个出现可以重叠。更新后，字符串变为 _ababcbaba_，现在 _aba_ 在区间 $[1, 7]$ 中仅出现一次。 ## Input 输入的第一行包含字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。第二行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——需要处理的查询数量。接下来的 $q$ 行描述查询，可能具有以下形式之一： $1\ i\ c$（$1 ≤ i ≤ |s|$） $2\ l\ r\ y$（$1 ≤ l ≤ r ≤ |s|$）其中 $c$ 是一个小写英文字母，$y$ 是一个仅由小写英文字母组成的非空字符串。所有第二类查询中 $|y|$ 的总和不超过 $10^5$。保证至少存在一个第二类查询。所有字符串均为 $1$-索引。$|s|$ 表示字符串 $s$ 的长度。 ## Output 对于每个第二类查询，请在单独一行中输出所需答案。 [samples] ## Note 考虑第一个样例。初始时，字符串 _aba_ 在区间 $[1, 7]$ 中出现 $3$ 次。注意，两个出现可以重叠。更新后，字符串变为 _ababcbaba_，现在 _aba_ 在区间 $[1, 7]$ 中仅出现一次。

**Definitions:** - Let $ s \in \Sigma^* $ be a string of length $ n = |s| $, where $ \Sigma $ is the set of lowercase English letters, and $ s $ is 1-indexed. - Let $ q \in \mathbb{N} $ be the number of queries. - Two types of queries: 1. **Update**: Replace the character at position $ c $ (1-indexed) with a new character (implicitly, the string $ s $ is modified). 2. **Query**: Given a non-empty pattern string $ y $, count the number of occurrences of $ y $ as a substring in the prefix $ s[1..7] $ (i.e., the first 7 characters of the current string $ s $). **Constraints:** - $ 1 \leq n \leq 10^5 $ - $ 1 \leq q \leq 10^5 $ - For each query of type 2, $ y \in \Sigma^+ $, and the total sum of $ |y| $ over all type-2 queries is $ \leq 10^5 $ - At least one query is of type 2. - All string indices are 1-based. **Objective:** For each query of type 2, compute: $$ \left| \left\{ i \in [1, 7 - |y| + 1] \mid s[i..i + |y| - 1] = y \right\} \right| $$ That is, the number of starting positions $ i $ in the range $ [1, 7 - |y| + 1] $ such that the substring of $ s $ from position $ i $ to $ i + |y| - 1 $ equals $ y $. **Note:** After each update query (type 1), the string $ s $ is modified in-place, and subsequent queries operate on the updated string.

Samples

Input #1

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

Output #1

3
1

Input #2

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

Output #2

2
2
1

API Response (JSON)

{
  "problem": {
    "name": "F. Substrings in a String",
    "description": {
      "content": "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_ s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF914F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given a string _s_, process _q_ queries, each having one of the following forms:\n\n*   1 _i_ _c_ — Change the _i_\\-th character in the string to _c_.\n*   2 _l_ _r_ _y_ — Consider the substring of _s_ s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个字符串 $s$，处理 $q$ 个查询，每个查询具有以下形式之一：\n\n输入的第一行包含字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。\n\n第二行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——需要处理的查询数量。\n\n接下来的 $q$ 行描述查询，可能具有以下形式之一：\n\n$1\\ i\\ c$（$1 ≤ i ≤ |s|$）\n\n$2\\ l\\ r\\ y$（$1 ≤ l...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n\n- Let $ s \\in \\Sigma^* $ be a string of length $ n = |s| $, where $ \\Sigma $ is the set of lowercase English letters, and $ s $ is 1-indexed.\n- Let $ q \\in \\mathbb{N} $ be the number...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments