String Hashing
Turn substrings into numbers with a polynomial hash so any two substrings compare in O(1), and know exactly when it can fail.
The problem
You have a string s of length up to 200,000 and many queries. Each query gives two substrings and asks whether they are equal. Comparing letter by letter costs the length of the substring.
1 of 10