1839. How Much Two Suffixes Share
A string s is given, then q questions. Each question gives two positions i and
j, and asks how many characters the suffix starting at i and the suffix
starting at j share at the front.
When i equals j the answer is the whole length of that suffix.
``` s = banana 1 3 -> 3 anana and ana agree for 3 0 2 -> 0 3 5 -> 1 1 1 -> 5 the suffix anana against itself
s = aaaa 0 1 -> 3 0 3 -> 1 ```
## What most people try first
Walk forward comparing. Each question costs up to 2 * 10^5 comparisons, so
2 * 10^5 questions cost 4 * 10^10. The method below answers each question
with two array reads after an O(n log n) setup, so about 4 * 10^5 for the
questions themselves.
## Neighbours in sorted order, then a minimum
Build the suffix array and the neighbour agreement array from problem 1838. Then
agreement(i, j) = the MINIMUM of the neighbour values
between rank[i] and rank[j] in sorted order
where rank[i] is the position of the suffix at i in the sorted order. If
rank[i] < rank[j], the range is lcp[rank[i] .. rank[j]-1].
Answer the minimum with a sparse table: precompute the minimum of every range whose length is a power of two, then cover any range with two overlapping such blocks.
## Why the minimum over the range is the answer
Sorted order puts suffixes sharing a long prefix next to each other. Walking
from rank[i] to rank[j] one step at a time, the shared prefix with the
ORIGINAL suffix can only shrink, and it shrinks to exactly the smallest
neighbour value seen on the way.
More precisely: every suffix between them in sorted order starts with the common prefix of the two ends, so the agreement never drops below the minimum; and the pair achieving the minimum shows it never rises above it.
## The boundary that is easy to miss
i == j is not a range at all, and the range lcp[rank[i] .. rank[i]-1] is
empty, which most minimum routines report as infinity or as a garbage value. The
answer there is n - i, the length of the suffix, and it needs its own line of
code.
## Cost
O(n log n) to build the sparse table, O(1) per question. The table is
n log n integers, about 3.6 * 10^6 at the limits, which is 14 megabytes at
four bytes each.
Constraints - `1 ≤ length of s ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ i < length of s` and `0 ≤ j < length of s` - `s` contains only lowercase English letters - `i` may equal `j`
Input
The first line contains the string s.
The second line contains the integer q.
Each of the next q lines contains two integers i and j, the 0-based starting positions of two suffixes.
Output
Print one integer on its own line for each question, in the order the questions arrive: how many characters the two suffixes share at the front. When the two positions are equal, print the length of that suffix.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.