Near-optimal computation of runs over general alphabet via non-crossing LCE queries

Maxime Crochemore*, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 linearlysortable 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. (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, where α(n) is the inverse Ackermann function, which yields an O(nα(n))-time algorithm for computing runs.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings
EditorsShunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
PublisherSpringer Verlag
Pages22-34
Number of pages13
ISBN (Print)9783319460482
DOIs
Publication statusPublished - 1 Jan 2016
Externally publishedYes
Event23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 - Beppu, Japan
Duration: 18 Oct 201620 Oct 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9954 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016
CountryJapan
CityBeppu
Period18/10/1620/10/16

Fingerprint

Dive into the research topics of 'Near-optimal computation of runs over general alphabet via non-crossing LCE queries'. Together they form a unique fingerprint.

Cite this