Crazy LCP
Time limit2sMemory limit512 MB
Given N strings and Q range queries, for each range [L, R] report the maximum longest common prefix over all pairs of distinct strings in that range.
- Level
Hard8 of 10
- Topics
- String, Trie, Segment tree, Divide and conquer
- Solved
- No attempts yet
Problem
In this problem you are given an array of strings, these strings are given unique indexes from 1 to N (in the same order as in the input). Then you are given Q queries, each query consists of 2 integers L and R, to answer the query you need to find a pair of strings with different indexes in the range from L to R (inclusive), where the length of the longest common prefix for these 2 strings is the maximum among all other possible pairs.
Input
Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases.
Each test case starts with a line containing an integer N (2 ≤ N ≤ 105) representing the number of strings followed by a line containing N non-empty strings of lower case English letters separated by a single space, representing the list of strings. The sum of lengths of the strings in each test case is not greater than 200,000.
Followed by a line containing an integer Q (1 ≤ Q ≤ 105) representing the number of queries followed by Q lines, each line will contain 2 integers separated by a space, 'L R', which represent a query as described above (1 ≤ L < R ≤ N).
Output
For each query print a single line containing an integer which is the maximum length of a longest common prefix as described above.
Hint
A prefix of string S is the first (from the left) 0 or more characters from S, and a common prefix between 2 strings is a string which is a prefix in both of them.