ML p(r)ior | Faster Longest Common Extension Queries in Strings over General Alphabets

Faster Longest Common Extension Queries in Strings over General Alphabets

2016-02-01
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.
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-11-30

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

Highlights - Most important sentences from the article

2019-02-14
1902.05224 | cs.DS

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

Highlights - Most important sentences from the article

2019-01-30

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

Highlights - Most important sentences from the article

2017-07-14
1707.04609 | cs.DS

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

Highlights - Most important sentences from the article

2018-10-28

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

Highlights - Most important sentences from the article

2019-02-25

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-12-19

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-12-22

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

Highlights - Most important sentences from the article

2018-12-21

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

Highlights - Most important sentences from the article

2018-04-23

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

Highlights - Most important sentences from the article

2019-01-30

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

Highlights - Most important sentences from the article

2018-02-19

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

Highlights - Most important sentences from the article