Time-Space Trade-offs for Longest Common Extensions

Philip Bille, Inge Li Gortz, Benjamin Sach, Hjalte Wedel Vildhoj

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    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(|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
    Publication statusPublished - 2012
    Event23rd Annual Symposium on Combinatorial Pattern Matchin - University of Helsinki, Helsinki, Finland
    Duration: 4 Jun 20126 Jun 2012
    Conference number: CPM 2012

    Conference

    Conference23rd Annual Symposium on Combinatorial Pattern Matchin
    NumberCPM 2012
    LocationUniversity of Helsinki
    Country/TerritoryFinland
    CityHelsinki
    Period04/06/201206/06/2012
    SeriesLecture Notes in Computer Science
    Volume7354
    ISSN0302-9743

    Fingerprint

    Dive into the research topics of 'Time-Space Trade-offs for Longest Common Extensions'. Together they form a unique fingerprint.

    Cite this