Longest common extensions in sublinear space
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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.
Originalsprog | Engelsk |
---|---|
Titel | Combinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings |
Redaktører | Ferdinando Cicalese, Ely Porat, Ugo Vaccaro |
Antal sider | 12 |
Forlag | Springer |
Publikationsdato | 2015 |
Sider | 65-76 |
ISBN (Trykt) | 978-3-319-19928-3 |
ISBN (Elektronisk) | 978-3-319-19929-0 |
DOI | |
Status | Udgivet - 2015 |
Begivenhed | 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 - Ischia Island, Italien Varighed: 29 jun. 2015 → 1 jul. 2015 |
Konference
Konference | 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 |
---|---|
Land | Italien |
By | Ischia Island |
Periode | 29/06/2015 → 01/07/2015 |
Navn | Lecture notes in computer science |
---|---|
Vol/bind | 9133 |
ISSN | 0302-9743 |
ID: 159824575