2026-08-14T17:31:00Z https://drops.dagstuhl.de/oai

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

Longest Common Extensions with Recompression I, Tomohiro Longest Common Extension (LCE) queries compressed data structure grammar compressed strings Straight-Line Program (SLP) Given two positions i and j in a string T of length N, a longest common extension (LCE) query asks for the length of the longest common prefix between suffixes beginning at i and j. A compressed LCE data structure stores T in a compressed form while supporting fast LCE queries. In this article we show that the recompression technique is a powerful tool for compressed LCE data structures. We present a new compressed LCE data structure of size O(z lg (N/z)) that supports LCE queries in O(lg N) time, where z is the size of Lempel-Ziv 77 factorization without self-reference of T. Given T as an uncompressed form, we show how to build our data structure in O(N) time and space. Given T as a grammar compressed form, i.e., a straight-line program of size n generating T, we show how to build our data structure in O(n lg (N/n)) time and O(n + z lg (N/z)) space. Our algorithms are deterministic and always return correct answers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomohiro I 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.18 urn:nbn:de:0030-drops-73234 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.18 eng https://creativecommons.org/licenses/by/3.0/legalcode