{"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$ without changing the order.\n\nEach 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$).\n\nYou 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]$.\n\n## Input\n\nThe 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.\n\nThe second line is a string $s$ ($|s| = n$), consisting only of lowercase Latin letters.\n\nThe third line is a string $t$ ($|t| = m$), consisting only of lowercase Latin letters.\n\nEach 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.\n\n## Output\n\nPrint $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]$.\n\n[samples]\n\n## Note\n\nIn the first example the queries are substrings: \"_cod_\", \"_deforces_\", \"_fo_\" and \"_for_\", respectively.","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$（$| a |$ 是字符串 $a$ 的长度）。\n\n你需要回答 $q$ 个查询：对于第 $i$ 个查询，你需要计算字符串 $t$ 在子串 $s [ l_i.. r_i ]$ 中的出现次数。\n\n第一行包含三个整数 $n$、$m$ 和 $q$（$1 \\leq n, m \\leq 10^3$，$1 \\leq q \\leq 10^5$）——分别表示字符串 $s$ 的长度、字符串 $t$ 的长度和查询次数。\n\n第二行是一个字符串 $s$（$| s | = n$），仅由小写拉丁字母组成。\n\n第三行是一个字符串 $t$（$| t | = m$），仅由小写拉丁字母组成。\n\n接下来的 $q$ 行每行包含两个整数 $l_i$ 和 $r_i$（$1 \\leq l_i \\leq r_i \\leq n$）——表示第 $i$ 个查询的参数。\n\n请输出 $q$ 行，第 $i$ 行应包含第 $i$ 个查询的答案，即字符串 $t$ 在子串 $s [ l_i.. r_i ]$ 中的出现次数。\n\n在第一个示例中，查询对应的子串分别为：\"_cod_\"、\"_deforces_\"、\"_fo_\" 和 \"_for_\"。\n\n## Input\n\n第一行包含三个整数 $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$ 个查询的参数。\n\n## Output\n\n请输出 $q$ 行，第 $i$ 行应包含第 $i$ 个查询的答案，即字符串 $t$ 在子串 $s [ l_i.. r_i ]$ 中的出现次数。\n\n[samples]\n\n## Note\n\n在第一个示例中，查询对应的子串分别为：\"_cod_\"、\"_deforces_\"、\"_fo_\" 和 \"_for_\"。","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 $ 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 $.\n\n**Constraints**  \n1. $ 1 \\le n, m \\le 10^3 $  \n2. $ 1 \\le q \\le 10^5 $  \n3. $ |s| = n $, $ |t| = m $  \n4. For each query $ i $: $ 1 \\le l_i \\le r_i \\le n $  \n\n**Objective**  \nFor each query $ i $, compute the number of occurrences of $ t $ in the substring $ s[l_i..r_i] $.  \n\nAn 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:  \n$$\ns[j..j+m-1] = t\n$$\n\nThus, for each query $ i $, the answer is:  \n$$\n\\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|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1016B","tags":["brute force","implementation"],"sample_group":[["10 3 4\ncodeforces\nfor\n1 3\n3 10\n5 6\n5 7","0\n1\n0\n1"],["15 2 3\nabacabadabacaba\nba\n1 15\n3 4\n2 14","4\n0\n3"],["3 5 2\naaa\nbaaab\n1 3\n1 1","0\n0"]],"created_at":"2026-03-03 11:00:39"}}