5255 : A56 - 문자열 해시
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
길이가 $N$ 인 문자열 $S$ 가 주어집니다. 다음 $Q$ 개의 쿼리를 처리하세요.
단, $S[l, r] $ 은 $S$ 의 $l$ 번째 문자부터 $r$ 번째 문자까지의 연속 부분 문자열을 의미합니다.
[제약 조건]
• $N, Q, a_i, b_i, c_i, d_i$ 는 정수입니다.
• $S$ 는 영소문자로 이루어진 문자열입니다.
• $1 \le N \le 200000$
• $1 \le Q \le 200000$
• $|S| = N$
• $1 \le a_i \le b_i \le N$
• $1 \le c_i \le d_i \le N$
• $b_i - a_i = d_i - c_i$
- $i$ 번째 쿼리: $S[a_i, b_i] $ 와 $S[c_i, d_i] $ 는 일치하는가?
단, $S[l, r] $ 은 $S$ 의 $l$ 번째 문자부터 $r$ 번째 문자까지의 연속 부분 문자열을 의미합니다.
[제약 조건]
• $N, Q, a_i, b_i, c_i, d_i$ 는 정수입니다.
• $S$ 는 영소문자로 이루어진 문자열입니다.
• $1 \le N \le 200000$
• $1 \le Q \le 200000$
• $|S| = N$
• $1 \le a_i \le b_i \le N$
• $1 \le c_i \le d_i \le N$
• $b_i - a_i = d_i - c_i$
입력 설명
첫째 줄에 $N, Q$ 가 주어집니다.
둘째 줄에 문자열 $S$ 가 주어집니다.
셋째 줄부터 $Q$ 개의 줄에 걸쳐 $a_i, b_i, c_i, d_i$ 가 주어집니다.
둘째 줄에 문자열 $S$ 가 주어집니다.
셋째 줄부터 $Q$ 개의 줄에 걸쳐 $a_i, b_i, c_i, d_i$ 가 주어집니다.
출력 설명
각 쿼리에 대해 일치하면 `Yes`, 일치하지 않으면 `No`를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 3
abcbabc
1 3 5 7
1 5 2 6
1 2 6 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
Yes
No
No