Longest common extensions in sublinear space
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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 (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(image found) 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 |
Editors | Ferdinando Cicalese, Ely Porat, Ugo Vaccaro |
Number of pages | 12 |
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
Conference | 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 |
---|---|
Land | Italy |
By | Ischia Island |
Periode | 29/06/2015 → 01/07/2015 |
Series | Lecture notes in computer science |
---|---|
Volume | 9133 |
ISSN | 0302-9743 |
ID: 159824575