Polynomial Rolling Hash: Truy Vấn Xâu Con Bằng Nhau O(1)

Algorithms Buổi 53 — String Hashing Strings
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho xâu ký tự S độ dài N (chỉ số tính từ 1 đến N) và Q truy vấn. Mỗi truy vấn gồm 4 số nguyên l1, r1, l2, r2, yêu cầu kiểm tra hai xâu con S[l1..r1] và S[l2..r2] có bằng nhau hay không.

Dữ liệu vào (Input)
  • Dòng 1: Xâu S (1 ≤ |S| ≤ 2 × 10^5).
  • Dòng 2: Số nguyên dương Q (1 ≤ Q ≤ 2 × 10^5).
  • Q dòng tiếp theo: Mỗi dòng gồm 4 số nguyên l1 r1 l2 r2.
Dữ liệu ra (Output)
  • Gồm Q dòng, mỗi dòng in YES nếu hai xâu con bằng nhau, ngược lại in NO.
Ví dụ mẫu
Sample Input 1
abacaba
3
1 3 5 7
1 2 2 3
1 1 7 7
Sample Output 1
YES
NO
YES
Draft saved