Hash Equal Substrings Problem

Hash Equal Substrings Problem — ExecCode Hard DSA Practice

Solve the Hash Equal Substrings problem on ExecCode. Free online hard DSA practice in String. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You compare two closed ranges of the same string and ask if those substrings are exactly equal. Rolling hashes (two moduli) compare in O(1) after O(n) prefix hashes. Randomized hashing is the probabilistic version of the same idea. Each query [l1, r1, l2, r2]. Append 1 if s[l1..r1] equals s[l2..r2], else 0. Ranges are inclusive. You are given: s — text queries — four-tuples Return 0/1 per query. The two ranges may overlap.

Examples

Input {'s': 'ababa', 'queries': [[0, 2, 2, 4], [0, 1, 1, 2], [0, 0, 4, 4]]}; Output [1, 0, 1]. Input {'s': 'aaa', 'queries': [[0, 1, 1, 2]]}; Output [1]. Input {'s': 'ab', 'queries': [[0, 0, 1, 1]]}; Output [0]

Constraints

Indices valid in tests Different lengths are never equal

Practice Hash Equal Substrings free on ExecCode. Browse DSA problems, topic map, and placement guides.