### Faster Longest Common Extension Queries in Strings over General Alphabets

**2016-02-01**

1602.00447 | cs.DS

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 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^*n)$. The main tools are difference covers and the
disjoint-sets data structure.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2017-12-13**

1712.04886 | cs.DS

We propose algorithms that, given the input string of length $n$ over integer
alphabet of size $\sig… show more

**2019-04-08**

1904.04228 | cs.DS

Burrows-Wheeler transform (BWT) is an invertible text transformation that,
given a text $T$ of lengt… show more

**2018-11-30**

1811.12779 | cs.DS

We describe the first self-indexes able to count and locate pattern
occurrences in optimal time with… show more

**2019-02-14**

1902.05224 | cs.DS

Converting a compressed format of a string into another compressed format
without an explicit decomp… show more

**2019-01-30**

1901.10722 | cs.DS

Palindromes are important objects in strings which have been extensively
studied from combinatorial,… show more

**2017-07-14**

1707.04609 | cs.DS

In this paper, we introduce a general framework for fine-grained reductions
of approximate counting … show more

**2018-10-28**

1810.11863 | cs.DS

We introduce fast-decodable indexing schemes for edit distance which can be
used to speed up edit di… show more

**2019-02-25**

1902.09228 | cs.DS

We consider the problem of designing succinct data structures for interval
graphs with $n$ vertices … show more

**2018-12-02**

1812.00359 | cs.DS

We consider two closely related problems of text indexing in a sub-linear
working space. The first p… show more

**2018-12-19**

1812.08101 | cs.DS

A $k$-antipower (for $k \ge 2$) is a concatenation of $k$ pairwise distinct
words of the same length… show more

**2018-11-03**

1811.01209 | cs.DS

We study the problem of supporting queries on a string $S$ of length $n$
within a space bounded by t… show more

**2017-12-22**

1712.08573 | cs.DS

In the longest common substring problem, we are given two strings of length
$n$ and must find a subs… show more

**2018-12-21**

1812.09120 | cs.DS

In this paper we study lower bounds for the fundamental problem of text
indexing with mismatches and… show more

**2018-04-23**

1804.08731 | cs.DS

In the longest common substring (LCS) problem, we are given two strings $S$
and $T$, each of length … show more

**2019-01-30**

1901.10633 | cs.DS

A maximal repetition, or run, in a string, is a periodically maximal
substring whose smallest period… show more

**2018-02-19**

1802.06545 | cs.DS

We consider a range of simply stated dynamic data structure problems on
strings. An update changes o… show more