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

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Combinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings
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 number: 26 http://www.cpm2015.di.unisa.it/

Conference

Conference	26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015)
Number	26
Country/Territory	Italy
City	Ischia Island
Period	29/06/2015 → 01/07/2015
Internet address	http://www.cpm2015.di.unisa.it/

Series	Lecture Notes in Computer Science
Volume	9133
ISSN	0302-9743

Access to Document

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

Paper 58Accepted author manuscript, 339 KB

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

@inproceedings{9587f9e305b04372a981c3c583fb5463,

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

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

booktitle = "Combinatorial Pattern Matching",

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

url = "http://www.cpm2015.di.unisa.it/",

}

Bille, P , Gørtz, IL, Knudsen, MBT, Lewenstein, M & Vildhøj, HW 2015, Longest Common Extensions in Sublinear Space. in 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

Longest Common Extensions in Sublinear Space. / Bille, Philip ; Gørtz, Inge Li; Knudsen, Mathias Bæk Tejs; Lewenstein, Moshe; Vildhøj, Hjalte Wedel.

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

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

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

N1 - Conference code: 26

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

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

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

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

M3 - Article in proceedings

SN - 978-3-319-19928-3

T3 - Lecture Notes in Computer Science

SP - 65

EP - 76

BT - Combinatorial Pattern Matching

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