B. Segment Occurrences

Codeforces

IDCF1016B

Time2000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

You are given two strings $s$ and $t$, both consisting only of lowercase Latin letters. The substring $s[l..r]$ is the string which is obtained by taking characters $s_l, s_{l + 1}, \dots, s_r$ without changing the order. Each of the occurrences of string $a$ in a string $b$ is a position $i$ ($1 \le i \le |b| - |a| + 1$) such that $b[i..i + |a| - 1] = a$ ($|a|$ is the length of string $a$). You are asked $q$ queries: for the $i$\-th query you are required to calculate the number of occurrences of string $t$ in a substring $s[l_i..r_i]$. ## Input The first line contains three integer numbers $n$, $m$ and $q$ ($1 \le n, m \le 10^3$, $1 \le q \le 10^5$) — the length of string $s$, the length of string $t$ and the number of queries, respectively. The second line is a string $s$ ($|s| = n$), consisting only of lowercase Latin letters. The third line is a string $t$ ($|t| = m$), consisting only of lowercase Latin letters. Each of the next $q$ lines contains two integer numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the arguments for the $i$\-th query. ## Output Print $q$ lines — the $i$\-th line should contain the answer to the $i$\-th query, that is the number of occurrences of string $t$ in a substring $s[l_i..r_i]$. [samples] ## Note In the first example the queries are substrings: "_cod_", "_deforces_", "_fo_" and "_for_", respectively.

给你两个字符串 $s$ 和 $t$，它们仅由小写拉丁字母组成。子串 $s [ l.. r ]$ 是通过按顺序取字符 $s_l, s_{l + 1}, \dots, s_r$ 而得到的字符串。字符串 $a$ 在字符串 $b$ 中的每次出现是指一个位置 $i$（$1 \leq i \leq | b | -| a | + 1$），满足 $b [ i.. i + | a | -1 ] = a$（$| a |$ 是字符串 $a$ 的长度）。你需要回答 $q$ 个查询：对于第 $i$ 个查询，你需要计算字符串 $t$ 在子串 $s [ l_i.. r_i ]$ 中的出现次数。第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n, m \leq 10^3$，$1 \leq q \leq 10^5$）——分别表示字符串 $s$ 的长度、字符串 $t$ 的长度和查询次数。第二行是一个字符串 $s$（$| s | = n$），仅由小写拉丁字母组成。第三行是一个字符串 $t$（$| t | = m$），仅由小写拉丁字母组成。接下来的 $q$ 行每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）——表示第 $i$ 个查询的参数。请输出 $q$ 行，第 $i$ 行应包含第 $i$ 个查询的答案，即字符串 $t$ 在子串 $s [ l_i.. r_i ]$ 中的出现次数。在第一个示例中，查询对应的子串分别为："_cod_"、"_deforces_"、"_fo_" 和 "_for_"。 ## Input 第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n, m \leq 10^3$，$1 \leq q \leq 10^5$）——分别表示字符串 $s$ 的长度、字符串 $t$ 的长度和查询次数。第二行是一个字符串 $s$（$| s | = n$），仅由小写拉丁字母组成。第三行是一个字符串 $t$（$| t | = m$），仅由小写拉丁字母组成。接下来的 $q$ 行每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）——表示第 $i$ 个查询的参数。 ## Output 请输出 $q$ 行，第 $i$ 行应包含第 $i$ 个查询的答案，即字符串 $t$ 在子串 $s [ l_i.. r_i ]$ 中的出现次数。 [samples] ## Note 在第一个示例中，查询对应的子串分别为："_cod_"、"_deforces_"、"_fo_" 和 "_for_"。

**Definitions** Let $ s \in \Sigma^n $ and $ t \in \Sigma^m $ be strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $. Let $ q \in \mathbb{Z}^+ $ be the number of queries. For each query $ i \in \{1, \dots, q\} $, let $ [l_i, r_i] $ denote a contiguous substring of $ s $, with $ 1 \le l_i \le r_i \le n $. **Constraints** 1. $ 1 \le n, m \le 10^3 $ 2. $ 1 \le q \le 10^5 $ 3. $ |s| = n $, $ |t| = m $ 4. For each query $ i $: $ 1 \le l_i \le r_i \le n $ **Objective** For each query $ i $, compute the number of occurrences of $ t $ in the substring $ s[l_i..r_i] $. An occurrence of $ t $ in $ s[l_i..r_i] $ is a position $ j \in \{l_i, l_i+1, \dots, r_i - m + 1\} $ such that: $$ s[j..j+m-1] = t $$ Thus, for each query $ i $, the answer is: $$ \left| \left\{ j \in \mathbb{Z} \mid l_i \le j \le r_i - m + 1 \text{ and } s[j..j+m-1] = t \right\} \right| $$

Samples

Input #1

10 3 4
codeforces
for
1 3
3 10
5 6
5 7

Output #1

Input #2

15 2 3
abacabadabacaba
ba
1 15
3 4
2 14

Output #2

4
0
3

Input #3

3 5 2
aaa
baaab
1 3
1 1

Output #3

0
0

API Response (JSON)

{
  "problem": {
    "name": "B. Segment Occurrences",
    "description": {
      "content": "You are given two strings $s$ and $t$, both consisting only of lowercase Latin letters. The substring $s[l..r]$ is the string which is obtained by taking characters $s_l, s_{l + 1}, \\dots, s_r$ witho",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1016B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two strings $s$ and $t$, both consisting only of lowercase Latin letters.\n\nThe substring $s[l..r]$ is the string which is obtained by taking characters $s_l, s_{l + 1}, \\dots, s_r$ witho...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你两个字符串 $s$ 和 $t$，它们仅由小写拉丁字母组成。\n\n子串 $s [ l.. r ]$ 是通过按顺序取字符 $s_l, s_{l + 1}, \\dots, s_r$ 而得到的字符串。\n\n字符串 $a$ 在字符串 $b$ 中的每次出现是指一个位置 $i$（$1 \\leq i \\leq | b | -| a | + 1$），满足 $b [ i.. i + | a | -1 ] = a$（$...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^n $ and $ t \\in \\Sigma^m $ be strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments