Time-Space Trade-offs for Longest Common Extensions

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Standard

Time-Space Trade-offs for Longest Common Extensions. / Bille, Philip; Gortz, Inge Li; Sach, Benjamin; Vildhoj, Hjalte Wedel.

Combinatorial Pattern Matching. ed. / Juha Kärkkäinen; Jens Stoye. Springer, 2012. p. 293-305 (Lecture Notes in Computer Science, Vol. 7354).

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Harvard

Bille, P, Gortz, IL, Sach, B & Vildhoj, HW 2012, 'Time-Space Trade-offs for Longest Common Extensions'. in J Kärkkäinen & J Stoye (eds), Combinatorial Pattern Matching. Springer, pp. 293-305. Lecture Notes in Computer Science, vol. 7354, , 10.1007/978-3-642-31265-6_24

APA

Bille, P., Gortz, I. L., Sach, B., & Vildhoj, H. W. (2012). Time-Space Trade-offs for Longest Common Extensions. In J. Kärkkäinen, & J. Stoye (Eds.), Combinatorial Pattern Matching. (pp. 293-305). Springer. (Lecture Notes in Computer Science, Vol. 7354). 10.1007/978-3-642-31265-6_24

CBE

Bille P, Gortz IL, Sach B, Vildhoj HW. 2012. Time-Space Trade-offs for Longest Common Extensions. Kärkkäinen J, Stoye J, editors. In Combinatorial Pattern Matching. Springer. pp. 293-305. (Lecture Notes in Computer Science, Vol. 7354). Available from: 10.1007/978-3-642-31265-6_24

MLA

Bille, Philip et al. "Time-Space Trade-offs for Longest Common Extensions". and Kärkkäinen, Juha Stoye, Jens (ed.). Combinatorial Pattern Matching. Springer. 2012. 293-305. (Lecture Notes in Computer Science, Volume 7354). Available: 10.1007/978-3-642-31265-6_24

Vancouver

Bille P, Gortz IL, Sach B, Vildhoj HW. Time-Space Trade-offs for Longest Common Extensions. In Kärkkäinen J, Stoye J, editors, Combinatorial Pattern Matching. Springer. 2012. p. 293-305. (Lecture Notes in Computer Science, Vol. 7354). Available from: 10.1007/978-3-642-31265-6_24

Author

Bille, Philip; Gortz, Inge Li; Sach, Benjamin; Vildhoj, Hjalte Wedel / Time-Space Trade-offs for Longest Common Extensions.

Combinatorial Pattern Matching. ed. / Juha Kärkkäinen; Jens Stoye. Springer, 2012. p. 293-305 (Lecture Notes in Computer Science, Vol. 7354).

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Bibtex

@inbook{52cf42841a3d418f9dbcc102d59fcfe3,
title = "Time-Space Trade-offs for Longest Common Extensions",
publisher = "Springer",
author = "Philip Bille and Gortz, {Inge Li} and Benjamin Sach and Vildhoj, {Hjalte Wedel}",
year = "2012",
doi = "10.1007/978-3-642-31265-6_24",
editor = "Juha Kärkkäinen and Jens Stoye",
isbn = "978-3-642-31264-9",
series = "Lecture Notes in Computer Science",
pages = "293-305",
booktitle = "Combinatorial Pattern Matching",

}

RIS

TY - GEN

T1 - Time-Space Trade-offs for Longest Common Extensions

A1 - Bille,Philip

A1 - Gortz,Inge Li

A1 - Sach,Benjamin

A1 - Vildhoj,Hjalte Wedel

AU - Bille,Philip

AU - Gortz,Inge Li

AU - Sach,Benjamin

AU - Vildhoj,Hjalte Wedel

PB - Springer

PY - 2012

Y1 - 2012

N2 - We revisit the longest common extension (LCE) problem, that is, preprocess a string T into a compact data structure that supports fast LCE queries. An LCE query takes a pair (i,j) of indices in T and returns the length of the longest common prefix of the suffixes of T starting at positions i and j. We study the time-space trade-offs for the problem, that is, the space used for the data structure vs. the worst-case time for answering an LCE query. Let n be the length of T. Given a parameter τ, 1 ≤ τ ≤ n, we show how to achieve either O(n/√τ) space and O(τ) query time, or O(n/τ) space and O(τ log(|LCE(i,j)|/τ)) query time, where |LCE(i,j)| denotes the length of the LCE returned by the query. These bounds provide the first smooth trade-offs for the LCE problem and almost match the previously known bounds at the extremes when τ = 1 or τ = n. We apply the result to obtain improved bounds for several applications where the LCE problem is the computational bottleneck, including approximate string matching and computing palindromes. Finally, we also present an efficient technique to reduce LCE queries on two strings to one string.

AB - We revisit the longest common extension (LCE) problem, that is, preprocess a string T into a compact data structure that supports fast LCE queries. An LCE query takes a pair (i,j) of indices in T and returns the length of the longest common prefix of the suffixes of T starting at positions i and j. We study the time-space trade-offs for the problem, that is, the space used for the data structure vs. the worst-case time for answering an LCE query. Let n be the length of T. Given a parameter τ, 1 ≤ τ ≤ n, we show how to achieve either O(n/√τ) space and O(τ) query time, or O(n/τ) space and O(τ log(|LCE(i,j)|/τ)) query time, where |LCE(i,j)| denotes the length of the LCE returned by the query. These bounds provide the first smooth trade-offs for the LCE problem and almost match the previously known bounds at the extremes when τ = 1 or τ = n. We apply the result to obtain improved bounds for several applications where the LCE problem is the computational bottleneck, including approximate string matching and computing palindromes. Finally, we also present an efficient technique to reduce LCE queries on two strings to one string.

U2 - 10.1007/978-3-642-31265-6_24

DO - 10.1007/978-3-642-31265-6_24

SN - 978-3-642-31264-9

BT - Combinatorial Pattern Matching

T2 - Combinatorial Pattern Matching

A2 - Stoye,Jens

ED - Stoye,Jens

T3 - Lecture Notes in Computer Science

T3 - en_GB

SP - 293

EP - 305

ER -