1826. Which of Two Pieces Comes First in the Dictionary
A string s is given, then q questions. Each question gives four 0-based indices
l1 r1 l2 r2, naming the pieces s[l1..r1] and s[l2..r2], both inclusive.
Print <, > or = according to which piece comes first in dictionary order.
Dictionary order compares character by character, and when one piece is a prefix of the other the SHORTER one comes first.
``` s = banana 0 2 1 3 -> > ban against ana, b is after a 1 3 3 5 -> = ana against ana 0 5 0 5 -> =
s = aaaa 0 0 0 1 -> < a against aa, the shorter one wins ```
## What most people try first
Compare the two pieces character by character. Each question costs up to
2 * 10^5 comparisons, so 2 * 10^5 questions cost 4 * 10^10. The method
below answers each question in about 18 steps, so about 3.6 * 10^6 in total.
The bad case is not rare. Any string with a long repeat, such as abc written
20000 times, makes almost every pair of pieces agree for thousands of characters
before diverging.
## Find where they diverge, then look at one character
L = binary search for the longest common prefix of the two pieces
if L equals both lengths: print =
else if L equals the first length: print < the first ran out
else if L equals the second length: print >
else compare s[l1 + L] with s[l2 + L]
The binary search uses substring hashes, which compare two blocks of a given
length in constant time. The property is monotone: if the first L characters
agree then so do the first L - 1.
## Why the three cases before the character comparison
If the common prefix runs to the end of one piece, there IS no character to
compare on that side. That is exactly the prefix rule, and it is where a
comparison written as a single character test reads past the end of a piece and
compares an unrelated character of s. On s = aaaa with pieces a and aa,
the search returns L = 1, the first piece is exhausted, and the answer is <
with no character compared at all.
## HASHING IS NOT EXACT, SO HERE IS THE PROBABILITY
TWO hashes are used, with different bases and different prime moduli near
10^9. A false equality needs both to collide, with probability about 10^-18
per comparison. A run makes at most q * 18, about 3.6 * 10^6, comparisons, so
the chance that any of them is wrong is below 4 * 10^-12.
The answer is correct with that probability, not with certainty. No verification
is performed, because verifying a claimed common prefix of length L costs
O(L) and would put the quadratic cost straight back.
## Overflow
The intermediate product h[i] * pow[L] reaches about 10^18, inside the
signed 64 bit limit of 9223372036854775807 and far outside a 32 bit one.
## Cost
O(n) setup and O(log n) per question.
Constraints - `1 ≤ length of s ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ l1 ≤ r1 < length of s` and `0 ≤ l2 ≤ r2 < length of s` - `s` contains only lowercase English letters - when one piece is a prefix of the other, the shorter piece comes first - nothing is matched here, so overlap does not arise, and one character is wanted per question
Input
The first line contains the string s.
The second line contains the integer q.
Each of the next q lines contains four integers l1 r1 l2 r2, the inclusive 0-based bounds of the two pieces.
Output
Print one character on its own line for each question, in the order the questions arrive: < if the first piece comes earlier in dictionary order, > if it comes later, and = if the two pieces are identical.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.