Conference paper · Book chapter
Longest Common Extensions in Sublinear Space
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≤τ≤n, the problem can be solved in O(n/τ) space and O(τ) query time. This significantly improves the previously best known time-space trade-offs, and almost matches the best known time-space product lower bound.
Language: | English |
---|---|
Publisher: | Springer |
Year: | 2015 |
Pages: | 65-76 |
Proceedings: | 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015) |
Series: | Lecture Notes in Computer Science |
Journal subtitle: | 26th Annual Symposium, Cpm 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings |
ISBN: | 3319199285 , 3319199293 , 9783319199283 and 9783319199290 |
ISSN: | 03029743 and 16113349 |
Types: | Conference paper and Book chapter |
DOI: | 10.1007/978-3-319-19929-0_6 |
ORCIDs: | 0000-0001-5308-9609 , Bille, Philip and Gørtz, Inge Li |