Range LCP

• The paper defines the Range LCP problem – a generalization of the LCP problem.
• The input of the problem is a range of indices in a preprocessed n-length string.
• The output is the pair of indices in the input range having the maximum LCP.
• The new concept of bridges and optimal bridges in a string is defined and used.
• After O(nlog2n) time processing, queries can be answered in O(loglogn) time.

In this paper, we define the Range LCP problem as follows. Preprocess a string S, of length n  , to enable efficient solutions of the following query: Given [i,j][i,j], 0