30724번 - Поиск подподстроки в подстроке 다국어

Опытным участникам соревнований по спортивному программированию хорошо известна классическая задача о нахождении количества вхождений подстроки в строку. Обычно она формулируется так: дана строка-образец $s$ и строка $t$, требуется найти количество индексов, начиная с которых строка $s$ содержится в строке $t$.

К сожалению, для решения этой задачи уже придумано множество алгоритмов, поэтому сама по себе она может быть интересна только в качестве упражнения, но не олимпиадной задачи. Однако, как это часто бывает со стандартными задачами, её легко усложнить --- представим, что нас интересуют не сами строки $s$ и $t$, а некоторые их подстроки $s[l_1 \ldots r_1]$ и $t[l_2 \ldots r_2]$.

Как вы уже, наверное, догадались, вам дано $q$ запросов, $i$-й из которых задаёт некоторые подстроки $\bar s = s[{l_1}_i \ldots {r_1}_i]$ и $\bar t = t[{l_2}_i \ldots {r_2}_i]$. Для каждого такого запроса необходимо посчитать количество вхождений строки $\bar s$ в строку $\bar t$.

Первая и вторая строки входных данных содержат строки $s$ и $t$ ($1 \le |s|, |t| \le 2 \cdot 10^5$) соответственно. Строки состоят из маленьких букв английского алфавита.

В третьей строке задано одно число $q$ ($1 \le q \le 5 \cdot 10^5$) --- количество запросов.

Каждая из следующих $q$ строк содержит по четыре числа $l_1$, $r_1$, $l_2$ и $r_2$ ($1 \le l_1 \le r_1 \le |s|, 1 \le l_2 \le r_2 \le |t|$), описывающих очередной запрос.

Выведите $q$ чисел --- ответы на запросы.

Рассмотрим запросы в первом примере. Для индексации позиций вхождения будем использовать изначальные позиции в строке $t$.

1. $\bar s = ab, \bar t = abababa$. $\bar s$ входит в $\bar t$, начиная с индексов $[1, 3, 5]$.
2. $\bar s = bb, \bar t = babababb$. $\bar s$ входит в $\bar t$, начиная с индекса $[8]$.
3. $\bar s = b, \bar t = baba$. $\bar s$ входит в $\bar t$, начиная с индексов $[4, 6]$.
4. $\bar s = ab, \bar t = bab$. $\bar s$ входит в $\bar t$, начиная с индекса $[3]$.
5. $\bar s = a, \bar t = ababababb$. $\bar s$ входит в $\bar t$, начиная с индексов $[1, 3, 5, 7]$.