8070 : 문자열 해싱
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
길이가 $N$인 문자열 $S$가 주어집니다.
이후 $M$개의 질의가 주어지며, 각 질의는 두 구간 $[a, b]$와 $[c, d]$의 부분 문자열이 서로 일치하는지 묻는 것입니다.
이 질문들에 대해 고속으로 처리하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le |S| \le 30{,}000$
• $1 \le M \le 30{,}000$ (질의 수)
• $1 \le a \le b \le |S|$, $1 \le c \le d \le |S|$
이후 $M$개의 질의가 주어지며, 각 질의는 두 구간 $[a, b]$와 $[c, d]$의 부분 문자열이 서로 일치하는지 묻는 것입니다.
이 질문들에 대해 고속으로 처리하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le |S| \le 30{,}000$
• $1 \le M \le 30{,}000$ (질의 수)
• $1 \le a \le b \le |S|$, $1 \le c \le d \le |S|$
입력 설명
첫째 줄에 알파벳 소문자로 구성된 문자열 $S$가 주어집니다. ($1 \le |S| \le 30{,}000$)
둘째 줄에 질의의 개수 $M$이 주어집니다. ($1 \le M \le 30{,}000$)
셋째 줄부터 $M$개의 줄에 걸쳐 각 질의를 나타내는 4개의 정수 $a, b, c, d$가 공백으로 구분되어 주어집니다. 이는 $S$의 $a$번째 문자부터 $b$번째 문자까지의 부분 문자열과 $c$번째부터 $d$번째까지의 부분 문자열을 의미합니다. (1-indexed)
둘째 줄에 질의의 개수 $M$이 주어집니다. ($1 \le M \le 30{,}000$)
셋째 줄부터 $M$개의 줄에 걸쳐 각 질의를 나타내는 4개의 정수 $a, b, c, d$가 공백으로 구분되어 주어집니다. 이는 $S$의 $a$번째 문자부터 $b$번째 문자까지의 부분 문자열과 $c$번째부터 $d$번째까지의 부분 문자열을 의미합니다. (1-indexed)
출력 설명
각 질의에 대하여 두 부분 문자열이 일치하면
1, 일치하지 않으면 0을 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
aybabtu
3
1 3 5 7
1 2 4 5
2 3 5 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
0
1도움
다항 롤링 해시(Polynomial Rolling Hash) 기법을 사용하면 $O(N)$에 전처리를 완료한 후 각 구간 해시 질의를 $O(1)$에 판별할 수 있습니다.