1822. How Far Two Places Agree
Two strings s and t are given, then q questions. Each question gives a
position i in s and a position j in t, and asks how many characters s
from i onwards and t from j onwards agree before they differ or one of them
runs out.
``` s = abcabc, t = abcxyz i=0, j=0 -> 3 abc, then a against x i=3, j=0 -> 3 i=1, j=1 -> 2 bc, then a against x
s = aaaa, t = aaaa i=1, j=0 -> 3 s runs out ```
## What most people try first
Walk both strings forward comparing. Each question costs up to 2 * 10^5
comparisons, so 2 * 10^5 questions cost about 4 * 10^10. The method below
answers each question in about 18 steps, so about 3.6 * 10^6 in total.
## Binary search on a length you can test in constant time
If the first L characters agree then so do the first L - 1, so the property
is monotone and a binary search applies. The test, "do these two blocks of
length L agree", is a comparison of two substring hashes:
lo = 0; hi = min(|s| - i, |t| - j)
while lo < hi:
mid = (lo + hi + 1) / 2
if hash(s, i, mid) == hash(t, j, mid): lo = mid
else: hi = mid - 1
answer = lo
Note (lo + hi + 1) / 2 and not (lo + hi) / 2. When lo = hi - 1 the plain
midpoint is lo itself, the test succeeds, lo does not move and the loop never
ends.
## HASHING IS NOT EXACT, SO HERE IS THE PROBABILITY
This problem does NOT verify its hits, because a verification would cost O(L)
and undo the whole point. Instead it uses TWO independent hashes, with different
bases and different prime moduli near 10^9, and treats two blocks as equal only
when both agree.
Two unequal strings collide under both at once with probability about
1 / (M1 * M2), which is about 10^-18. The run makes at most
q * log2(2 * 10^5), about 3.6 * 10^6, comparisons, so the chance that ANY
comparison in a whole run is wrong is below 4 * 10^-12.
That is the honest statement: the answer is correct with probability at least
1 - 4 * 10^-12, not with certainty. A single hash modulo 10^9 would give
about 3.6 * 10^-3 instead, which is one wrong run in three hundred.
## Overflow
Each hash is below 10^9, and the intermediate product h[i] * pow[L] reaches
about 10^18. That fits in a signed 64 bit integer, whose limit is
9223372036854775807, and overflows a 32 bit one by a factor of 4 * 10^8.
## Cost
O(|s| + |t|) setup and O(log) per question.
Constraints - `1 ≤ length of s ≤ 200000` - `1 ≤ length of t ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ i < length of s` and `0 ≤ j < length of t` - both strings contain only lowercase English letters - nothing is matched here, so overlap does not arise, and one length is wanted per question
Input
The first line contains the string s.
The second line contains the string t.
The third line contains the integer q.
Each of the next q lines contains two integers i and j, a 0-based position in s and a 0-based position in t.
Output
Print one integer on its own line for each question, in the order the questions arrive: the number of characters by which s from position i and t from position j agree before differing or running out.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.