2026-07-24T00:34:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8102 2024-03-06T10:40:50Z ddc:004 open_access

Small-Space LCE Data Structure with Constant-Time Queries Tanimura, Yuka Nishimoto, Takaaki Bannai, Hideo Inenaga, Shunsuke Takeda, Masayuki longest common extension truncated suffix trees t-covers The longest common extension (LCE) problem is to preprocess a given string w of length n so that the length of the longest common prefix between suffixes of w that start at any two given positions is answered quickly. In this paper, we present a data structure of O(z \tau^2 + \frac{n}{\tau}) words of space which answers LCE queries in O(1) time and can be built in O(n \log \sigma) time, where 1 \leq \tau \leq \sqrt{n} is a parameter, z is the size of the Lempel-Ziv 77 factorization of w and \sigma is the alphabet size. The proposed LCE data structure not access the input string w when answering queries, and thus w can be deleted after preprocessing. On top of this main result, we obtain further results using (variants of) our LCE data structure, which include the following: - For highly repetitive strings where the z\tau^2 term is dominated by \frac{n}{\tau}, we obtain a constant-time and sub-linear space LCE query data structure. - Even when the input string is not well compressible via Lempel-Ziv 77 factorization, we still can obtain a constant-time and sub-linear space LCE data structure for suitable \tau and for \sigma \leq 2^{o(\log n)}. - The time-space trade-off lower bounds for the LCE problem by Bille et al. [J. Discrete Algorithms, 25:42-50, 2014] and by Kosolobov [CoRR, abs/1611.02891, 2016] do not apply in some cases with our LCE data structure. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuka Tanimura and Takaaki Nishimoto and Hideo Bannai and Shunsuke Inenaga and Masayuki Takeda 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.10 urn:nbn:de:0030-drops-81021 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.10 eng https://creativecommons.org/licenses/by/3.0/legalcode