Abstract
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.
Original language | English |
---|---|
Title of host publication | Combinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings |
Publisher | Springer |
Publication date | 2015 |
Pages | 65-76 |
ISBN (Print) | 978-3-319-19928-3 |
ISBN (Electronic) | 978-3-319-19929-0 |
DOIs | |
Publication status | Published - 2015 |
Event | 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015) - Ischia Island, Italy Duration: 29 Jun 2015 → 1 Jul 2015 Conference number: 26 http://www.cpm2015.di.unisa.it/ |
Conference
Conference | 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015) |
---|---|
Number | 26 |
Country/Territory | Italy |
City | Ischia Island |
Period | 29/06/2015 → 01/07/2015 |
Internet address |
Series | Lecture Notes in Computer Science |
---|---|
Volume | 9133 |
ISSN | 0302-9743 |