Polynomial Rolling Hash: Truy Vấn Xâu Con Bằng Nhau O(1)
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
string
Đề 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). Qdòng tiếp theo: Mỗi dòng gồm 4 số nguyênl1 r1 l2 r2.
Dữ liệu ra (Output)
- Gồm
Qdòng, mỗi dòng inYESnếu hai xâu con bằng nhau, ngược lại inNO.
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
Community Discussion