Longest common extensions in sublinear space

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

  • Philip Bille
  • Inge Li Gørtz
  • Mathias Bæk Tejs Knudsen
  • Moshe Lewenstein
  • Hjalte Wedel Vildhøj

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.

OriginalsprogEngelsk
TitelCombinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings
RedaktørerFerdinando Cicalese, Ely Porat, Ugo Vaccaro
Antal sider12
ForlagSpringer
Publikationsdato2015
Sider65-76
ISBN (Trykt)978-3-319-19928-3
ISBN (Elektronisk)978-3-319-19929-0
DOI
StatusUdgivet - 2015
Begivenhed26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 - Ischia Island, Italien
Varighed: 29 jun. 20151 jul. 2015

Konference

Konference26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
LandItalien
ByIschia Island
Periode29/06/201501/07/2015
NavnLecture notes in computer science
Vol/bind9133
ISSN0302-9743

ID: 159824575