Truy vấn xâu đối xứng

[huy2k2ndt2]

Cho xâu S có độ dài n chỉ gồm các kí tự 0 hoặc 1. Cho m truy vấn có dạng L R, với mỗi truy vấn, kiểm tra xem đoạn con từ L đến R của xâu S có phải là xâu đối xứng hay không. In ra YES nếu đoạn con là xâu đối xứng và NO nếu ngược lại.
Input #3

1101111111111
5
4 8
1 9
5 9
9 13
10 13

Output #3

YES
NO
YES
YES
YES
mn cho mình ý tưởng làm bài này với ạ

[rogp10]

Định nghĩa đối xứng là string == string.reverse()
Để phủ định nhanh chóng người ta sẽ dùng 1 tiêu chuẩn “lỏng” hơn là hash(string) == hash(string.reverse()). Mục tiêu là chuẩn bị các giá trị này trong O(N).

hint

bằng hàm đa thức

[huy2k2ndt2]

ok cảm ơn b nhiều …trước h mình toàn duyệt mà ko biết cách dùng này