King's College London

Research portal

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

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

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

Original languageEnglish
Title of host publicationString Processing and Information Retrieval
Subtitle of host publication23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings
EditorsShunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
Place of PublicationCham
PublisherSpringer International Publishing Switzerland
Pages22-34
Number of pages13
ISBN (Print)9783319460499
DOIs
Publication statusE-pub ahead of print - 21 Sep 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9954
ISSN (Print)0302-9743

Documents

King's Authors

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(logn)2/3)-time algorithm for answering O(n) LCE queries. This result was improved by Gawrychowski et al. (CPM 2016) to O(nloglogn) 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.

Download statistics

No data available

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454