Skip to main content

Practice · 5 of 5

Truy vấn đoạn bằng nhau

CHALLENGE
Difficulty: intermediate+25 XP

**Bài toán.** Xâu s (≤ 2·10^5), Q truy vấn (l1, r1, l2, r2): đoạn s[l1..r1] và s[l2..r2] (đánh số từ 1) BẰNG NHAU? In YES/NO mỗi truy vấn (mỗi kết quả một dòng). **Ràng buộc:** 1 ≤ Q ≤ 2·10^5; 1 ≤ l1 ≤ r1 ≤ |s|; 1 ≤ l2 ≤ r2 ≤ |s|; độ dài hai đoạn LUÔN bằng nhau. Băm tiền tố trả O(1) mỗi truy vấn; so ký tự trực tiếp O(n) mỗi truy vấn sẽ chết (2·10^5 × 2·10^5).

Back to lesson: Practice: String Techniques Problem Set