Longest Common Extension
Answer Q queries: given positions i and j in S, how long is the longest common substring starting simultaneously at i and at j?
Input: the first line has S; the second line has Q; each of the next Q lines has two 1-based positions i and j.
Output: one line per query with the LCE length.
Constraints:
- 1 ≤ |S| ≤ 105
- 1 ≤ Q ≤ 105
Sample Tests
Input 1
abcabc 2 1 4 1 2
Output 1
3 0
Input 2
aa 1 1 2
Output 2
1
Discussion (opens after you solve — no spoilers before)
No comments yet.