CF1016B Segment Occurrences

给定两个仅由小写拉丁字母组成的字符串 $s$ 和 $t$。 子串 $s[l..r]$ 表示取出 $s$ 的第 $l$ 个字符到第 $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]$ 中出现的次数。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m \le 10^3$，$1 \le q \le 10^5$），分别表示字符串 $s$ 的长度、字符串 $t$ 的长度和询问的数量。 第二行为一个长度为 $n$ 的字符串 $s$，仅包含小写拉丁字母。 第三行为一个长度为 $m$ 的字符串 $t$，仅包含小写拉丁字母。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 个询问的参数。

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

在第一个样例中，询问的子串分别为："cod"、"deforces"、"fo" 和 "for"。 由 ChatGPT 4.1 翻译