Faster longest common extension queries in strings over general alphabets

DOI10.4230/LIPICS.CPM.2016.5zbMATH Open1380.68474arXiv1602.00447OpenAlexW2963452431MaRDI QIDQ5369537FDOQ5369537

Authors: Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Waleń 

Publication date: 17 October 2017

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(qloglogn+nlo{g}^{\ast }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(nloglogn)$ time making $O(n)$ symbol comparisons. Our results improve upon a solution by Kosolobov (Information Processing Letters, 2016), who gave an algorithm with $O(nlo{g}^{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(qlogn+nlo{g}^{\ast }n)$. The main tools are difference covers and the disjoint-sets data structure.

Full work available at URL: https://arxiv.org/abs/1602.00447

Recommendations

• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• Longest common extensions via fingerprinting
• Faster range LCP queries
• The longest common extension problem revisited and applications to approximate string searching
• Longest common extensions in sublinear space

zbMATH Keywords

longest common prefixdifference coverlongest common extensionmaximal repetitions

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Cited In (15)

• Optimal bounds for computing \({\alpha}\)-gapped repeats
• On the size of the smallest alphabet for Lyndon trees
• Computing longest common extensions in partial words
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Tight lower bounds for the longest common extension problem
• Time-Space Trade-Offs for Longest Common Extensions
• Longest property-preserved common factor: a new string-processing framework
• Absent Subsequences in Words
• Near-optimal quantum algorithms for string problems
• Small-space LCE data structure with constant-time queries
• Almost linear time computation of maximal repetitions in run length encoded strings
• Computing runs on a trie
• Searching runs in streams
• Cartesian and Lyndon trees
• On the size of overlapping Lempel-Ziv and Lyndon factorizations

This page was built for publication: Faster longest common extension queries in strings over general alphabets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369537)