부분 문자열 속의 부분 문자열

시간 제한2초메모리 제한1024 MB

요약

각 질의마다 문자열 s의 부분 문자열 s[l1..r1]이 문자열 t의 부분 문자열 t[l2..r2]에 몇 번 나타나는지 셉니다.

난이도: 어려움10점 중 9점
유형: 문자열 매칭, 이분 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

스포츠 프로그래밍 대회에 익숙한 참가자라면 문자열 안에 패턴 문자열이 몇 번 나오는지 세는 고전 문제를 잘 알고 있을 것이다. 보통 이렇게 정의한다. 패턴 문자열 $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$ 에서의 인덱스로 나타낸다.

$\bar s = ab$ , $\bar t = abababa$ . $\bar s$ 는 인덱스 $[1, 3, 5]$ 에서 시작해 $\bar t$ 에 나타난다.
$\bar s = bb$ , $\bar t = babababb$ . $\bar s$ 는 인덱스 $[8]$ 에서 시작해 $\bar t$ 에 나타난다.
$\bar s = b$ , $\bar t = baba$ . $\bar s$ 는 인덱스 $[4, 6]$ 에서 시작해 $\bar t$ 에 나타난다.
$\bar s = ab$ , $\bar t = bab$ . $\bar s$ 는 인덱스 $[3]$ 에서 시작해 $\bar t$ 에 나타난다.
$\bar s = a$ , $\bar t = ababababb$ . $\bar s$ 는 인덱스 $[1, 3, 5, 7]$ 에서 시작해 $\bar t$ 에 나타난다.

예제1

예제 1

입력

abb
ababababb
5
1 2 1 7
2 3 2 9
3 3 4 7
1 2 2 4
1 1 1 9

예상 출력