| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 430215 | Journal of Computer and System Sciences | 2014 | 9 Pages |
Abstract
•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
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Amihood Amir, Alberto Apostolico, Gad M. Landau, Avivit Levy, Moshe Lewenstein, Ely Porat,