2026-09-18T02:43:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23815 2026-09-05T18:31:41Z ddc:004 open_access

Faster Range LCP Queries in Linear Space Nekirch, Yakov Thankachan, Sharma V. Data Structures String Algorithms Longest Common Prefix A range LCP query rlcp(α,β) on a text T[1 .. n] asks to return the length of the longest common prefix of any two suffixes of T with starting positions in a range [α,β]. In this paper we describe a data structure that uses O(n) space and supports range LCP queries in time O(log^ε n) for any constant ε > 0. Our result is the fastest currently known linear-space solution for this problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yakov Nekirch and Sharma V. Thankachan 2025 Is Part Of OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Grossi.16 urn:nbn:de:0030-drops-238158 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.16 eng https://creativecommons.org/licenses/by/4.0/legalcode