Journal
JOURNAL OF DISCRETE ALGORITHMS
Volume 25, Issue -, Pages 42-50Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.jda.2013.06.003
Keywords
Longest common extension; Approximate string matching; Palindrome; Tandem repeat; Time-space trade-off
Categories
Funding
- EPSRC
- EPSRC [EP/H028056/1] Funding Source: UKRI
Ask authors/readers for more resources
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 tau, 1 <= tau <= n, we show how to achieve either O(n/ root tau) space and O(tau) query time, or O(n/tau) space and O(tau log(vertical bar LCE(i, j)vertical bar/tau)) query time, where vertical bar LCE(i, j)vertical bar 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 tau = 1 or tau = 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. We also present an efficient technique to reduce LCE queries on two strings to one string. Finally, we give a lower bound on the time-space product for LCE data structures in the nonuniform cell probe model showing that our second trade-off is nearly optimal. (C) 2013 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available