|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
The longest common extension problem (LCE problem) is to construct a data structure for an input string T of length n that supports LCE(i,j) queries. Such a query returns the length of the longest common prefix of the suffixes starting at positions i and j in T. This classic problem has a well-known solution that uses O(n) space and O(1) query time. In this paper we show that for any trade-off parameter 1 <= t <= n, the problem can be solved in O(n/t) space and O(t) query time. This significantly improves the previously best known time-space trade-offs, and almost matches the best known time-space product lower bound. Host: Kim S. Larsen SDU HOME | IMADA HOME | Previous Page Daniel Merkle |