Faster Longest Common Extension Queries in Strings over General Alphabets

2016/02/01 by Gawrychowski, Paweł, Kociumaka, Tomasz, Rytter, Wojciech +1
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1602.00447

Abstract

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+nlog^*n) time making only O(q+n) symbol comparisons. Consequently, all runs in a string over a general ordered alphabet 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 gave an algorithm with O(n log^2/3 n) running time and conjectured that O(n) time is possible. We make a significant progress towards resolving this conjecture. Our techniques extend to the case of general unordered alphabets, when the time increases to O(qlog n + nlog^*n). The main tools are difference covers and the disjoint-sets data structure.

Related

• Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries
• Time-Space Trade-Offs for Longest Common Extensions
• Tight Lower Bounds for the Longest Common Extension Problem
• Longest Common Extensions in Sublinear Space
• Deterministic sub-linear space LCE data structures with efficient construction