2026-07-23T20:15:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6081 2024-03-06T10:37:33Z ddc:004 open_access

Faster Longest Common Extension Queries in Strings over General Alphabets Gawrychowski, Pawel Kociumaka, Tomasz Rytter, Wojciech Walen, Tomasz longest common extension longest common prefix maximal repetitions difference cover Longest common extension queries (often called longest common prefix queries) constitute a fundamental building block in multiple string algorithms, for example computing runs and approximate pattern matching. We show that a sequence of q LCE queries for a string of size n over a general ordered alphabet can be realized in O(q log log n + n log* n) time making only O(q + n) symbol comparisons. Consequently, all runs in a string over a general ordered alphabets can be computed in O(n log log n) time making O(n) symbol comparisons. Our results improve upon a solution by Kosolobov (Information Processing Letters, 2016), who designed an algorithm with O(n log^⅔ n) running time and conjectured that O(n) time is possible. Our paper makes a significant progress towards resolving this conjecture. Our techniques extend to the case of general unordered alphabets, when the time increases to O(q log n + n log* n). The main tools are difference covers and a variant of the disjoint-sets data structure by La Poutré (SODA 1990). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Gawrychowski and Tomasz Kociumaka and Wojciech Rytter and Tomasz Walen 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.5 urn:nbn:de:0030-drops-60810 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.5 eng https://creativecommons.org/licenses/by/3.0/legalcode