Time-Space Trade-offs for Longest Common Extensions

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

View graph of relations

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.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
EditorsJuha Kärkkäinen, Jens Stoye
PublisherSpringer
Publication date2012
Pages293-305
ISBN (print)978-3-642-31264-9
DOIs
StatePublished

Conference

Conference23rd Annual Symposium on Combinatorial Pattern Matchin
NumberCPM 2012
CountryFinland
CityHelsinki
Period04/06/1206/06/12
NameLecture Notes in Computer Science
Volume7354
ISSN (Print)0302-9743
CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 10214470