Faster Longest Common Extension Queries in Strings over General Alphabets

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+n{\log }^{\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(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(q\log n+n{\log }^{\ast }n)$. The main tools are difference covers and the disjoint-sets data structure.

Accepted to CPM 2016

References in corpus (2)

• The "Runs" Theorem
• Lempel-Ziv Factorization May Be Harder Than Computing All Runs