Substring Equality Queries

Given a string s and queries [l1, r1, l2, r2] (0-indexed, inclusive), return an array of booleans indicating whether s[l1..r1] == s[l2..r2].

Function signature

func SubstringEquality(s string, queries [][]int) []bool

Example

s = "abracadabra"
queries = [[0,3,7,10],[0,2,3,5]]
output = [true,false]

Constraints

• 0 <= len(s) <= 200_000
• 0 <= len(queries) <= 200_000
• 0 <= l1 <= r1 < len(s)
• 0 <= l2 <= r2 < len(s)

Notes

• Use rolling hash (preferably double hash) for O(1) substring checks.