Longest Common Extensions in Sublinear Space

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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

208 Downloads (Pure)

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 languageEnglish
Title of host publicationCombinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings
PublisherSpringer
Publication date2015
Pages65-76
ISBN (Print)978-3-319-19928-3
ISBN (Electronic)978-3-319-19929-0
DOIs
Publication statusPublished - 2015
Event26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015) - Ischia Island, Italy
Duration: 29 Jun 20151 Jul 2015
Conference number: 26
http://www.cpm2015.di.unisa.it/

Conference

Conference26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015)
Number26
Country/TerritoryItaly
CityIschia Island
Period29/06/201501/07/2015
Internet address
SeriesLecture Notes in Computer Science
Volume9133
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Longest Common Extensions in Sublinear Space'. Together they form a unique fingerprint.

Cite this