The Library
Time-space trade-offs for longest common extensions
Tools
Tools
Tools
Bille, Philip, Gørtz, Inge Li, Sach, Benjamin and Vildhøj, Hjalte Wedel (2012) Time-space trade-offs for longest common extensions. Combinatorial Pattern Matching, Volume 7354 . pp. 293-305. doi:10.1007/978-3-642-31265-6_24
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/978-3-642-31265-6_24
Abstract
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(|\ensuremathLCE(i,j)|/τ)) query time, where |\ensuremathLCE(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.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science > Computer Science | ||||
| Journal or Publication Title: | Combinatorial Pattern Matching | ||||
| Publisher: | Springer | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Combinatorial Pattern Matching | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| Volume: | Volume 7354 | ||||
| Page Range: | pp. 293-305 | ||||
| DOI: | 10.1007/978-3-642-31265-6_24 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
