Longest common extensions in sublinear space

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

doi:10.1007/978-3-319-19929-0_6

Longest common extensions in sublinear space

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

^*Corresponding author for this work

Department of Computer Science

19 Citations (Scopus)

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 (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	https://doi.org/10.1007/978-3-319-19929-0_6
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
Country/Territory	Italy
City	Ischia Island
Period	29/06/2015 → 01/07/2015

Series	Lecture notes in computer science
Volume	9133
ISSN	0302-9743

Access to Document

10.1007/978-3-319-19929-0_6

Cite this

Bille, P., Gørtz, I. L., Knudsen, M. B. T., Lewenstein, M., & Vildhøj, H. W. (2015). Longest common extensions in sublinear space. In F. Cicalese, E. Porat, & U. Vaccaro (Eds.), Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings (pp. 65-76). Springer. Lecture notes in computer science Vol. 9133 https://doi.org/10.1007/978-3-319-19929-0_6

Longest common extensions in sublinear space. / Bille, Philip; Gørtz, Inge Li; Knudsen, Mathias Bæk Tejs et al.

Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings. ed. / Ferdinando Cicalese; Ely Porat; Ugo Vaccaro. Springer, 2015. p. 65-76 (Lecture notes in computer science, Vol. 9133).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Bille, P, Gørtz, IL, Knudsen, MBT, Lewenstein, M & Vildhøj, HW 2015, Longest common extensions in sublinear space. in F Cicalese, E Porat & U Vaccaro (eds), Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings. Springer, Lecture notes in computer science, vol. 9133, pp. 65-76, 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015, Ischia Island, Italy, 29/06/2015. https://doi.org/10.1007/978-3-319-19929-0_6

Bille P, Gørtz IL, Knudsen MBT, Lewenstein M, Vildhøj HW. Longest common extensions in sublinear space. In Cicalese F, Porat E, Vaccaro U, editors, Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings. Springer. 2015. p. 65-76. (Lecture notes in computer science, Vol. 9133). doi: 10.1007/978-3-319-19929-0_6

Bille, Philip ; Gørtz, Inge Li ; Knudsen, Mathias Bæk Tejs et al. / Longest common extensions in sublinear space. Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings. editor / Ferdinando Cicalese ; Ely Porat ; Ugo Vaccaro. Springer, 2015. pp. 65-76 (Lecture notes in computer science, Vol. 9133).

@inproceedings{47035ff52c3b4db7b05c26a0f2424fe9,

title = "Longest common extensions in sublinear space",

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 (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.",

author = "Philip Bille and G{\o}rtz, {Inge Li} and Knudsen, {Mathias B{\ae}k Tejs} and Moshe Lewenstein and Vildh{\o}j, {Hjalte Wedel}",

year = "2015",

doi = "10.1007/978-3-319-19929-0_6",

language = "English",

isbn = "978-3-319-19928-3",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "65--76",

editor = "Ferdinando Cicalese and Ely Porat and Ugo Vaccaro",

booktitle = "Combinatorial Pattern Matching",

note = "26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 ; Conference date: 29-06-2015 Through 01-07-2015",

}

TY - GEN

T1 - Longest common extensions in sublinear space

AU - Bille, Philip

AU - Gørtz, Inge Li

AU - Knudsen, Mathias Bæk Tejs

AU - Lewenstein, Moshe

AU - Vildhøj, Hjalte Wedel

PY - 2015

Y1 - 2015

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

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

U2 - 10.1007/978-3-319-19929-0_6

DO - 10.1007/978-3-319-19929-0_6

M3 - Article in proceedings

AN - SCOPUS:84948951020

SN - 978-3-319-19928-3

T3 - Lecture notes in computer science

SP - 65

EP - 76

BT - Combinatorial Pattern Matching

A2 - Cicalese, Ferdinando

A2 - Porat, Ely

A2 - Vaccaro, Ugo

PB - Springer

T2 - 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015

Y2 - 29 June 2015 through 1 July 2015

ER -

Longest common extensions in sublinear space

Abstract

Conference

Access to Document

Fingerprint

Cite this