CF1016B.Segment Occurrences

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]$.

给你两个字符串 $s$ 和 $t$，它们均由小写拉丁字母组成。

子串 $s[l..r]$ 是指按顺序取出字符 $s_l, s_{l + 1}, \dots, s_r$ 所构成的字符串。

字符串 $a$ 在字符串 $b$ 中的每一次出现，是指一个位置 $i$（满足 $1 \le i \le |b| - |a| + 1$），使得 $b[i..i + |a| - 1] = a$（其中 $|a|$ 表示字符串 $a$ 的长度）。

你需要处理 $q$ 个查询：对于第 $i$ 个查询，你需要计算字符串 $t$ 在子串 $s[l_i..r_i]$ 中的出现次数。

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.

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m \le 10^3$，$1 \le q \le 10^5$），分别表示字符串 $s$ 的长度、字符串 $t$ 的长度以及查询次数。

第二行是一个字符串 $s$（$|s| = n$），仅由小写拉丁字母组成。

第三行是一个字符串 $t$（$|t| = m$），仅由小写拉丁字母组成。

接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 次查询的参数。

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]$.

输出 $q$ 行——第 $i$ 行应包含第 $i$ 个查询的答案，即字符串 $t$ 在子串 $s[l_i..r_i]$ 中出现的次数。

In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.

在第一个例子中，查询字符串分别是子串：“cod”、“deforces”、“fo”和“for”。