Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries

Abstract : Longest common extension queries (LCE queries) and runs are ubiquitous in algorithmic stringology. Linear-time algorithms computing runs and preprocessing for constant-time LCE queries have been known for over a decade. However, these algorithms assume a linearly-sortable integer alphabet. A recent breakthrough paper by Bannai et. al. (SODA 2015) showed a link between the two notions: all the runs in a string can be computed via a linear number of LCE queries. The first to consider these problems over a general ordered alphabet was Kosolobov (Inf. Process. Lett., 2016), who presented an O(n(log n) 2/3)-time algorithm for answering O(n) LCE queries. This result was improved by Gawrychowski et. al. (accepted to CPM 2016) to O(n log log n) time. In this work we note a special non-crossing property of LCE queries asked in the runs computation. We show that any n such non-crossing queries can be answered on-line in O(nα(n)) time, which yields an O(nα(n))-time algorithm for computing runs.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01806286
Contributor : Maxime Crochemore <>
Submitted on : Friday, June 1, 2018 - 6:42:11 PM
Last modification on : Wednesday, June 6, 2018 - 10:22:51 AM
Long-term archiving on: Sunday, September 2, 2018 - 4:13:55 PM

File

lyndons_runs.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01806286, version 1

Collections

Citation

Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka, Ritu Kundu, Solon Pissis, et al.. Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries. String Processing and Information Retrieval, 2016, Beppu, Japan. ⟨hal-01806286⟩

Share

Metrics

Record views

46

Files downloads

106