Longest common extensions in sublinear space

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

  • 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.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings
EditorsFerdinando Cicalese, Ely Porat, Ugo Vaccaro
Number of pages12
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

Conference26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
LandItaly
ByIschia Island
Periode29/06/201501/07/2015
SeriesLecture notes in computer science
Volume9133
ISSN0302-9743

ID: 159824575