TY - CHAP

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

AU - Crochemore, Maxime

AU - Iliopoulos, Costas S.

AU - Kociumaka, Tomasz

AU - Kundu, Ritu

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

AU - Rytter, Wojciech

AU - Walen, Tomasz

PY - 2016/9/21

Y1 - 2016/9/21

N2 - 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.

AB - 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.

UR - http://arxiv.org/abs/1606.08275

U2 - 10.1007/978-3-319-46049-9_3

DO - 10.1007/978-3-319-46049-9_3

M3 - Other chapter contribution

SN - 9783319460499

T3 - Lecture Notes in Computer Science

SP - 22

EP - 34

BT - String Processing and Information Retrieval

A2 - Inenaga, Shunsuke

A2 - Sadakane, Kunihiko

A2 - Sakai, Tetsuya

PB - Springer International Publishing Switzerland

CY - Cham

ER -