TY - GEN
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 - Waleń, Tomasz
PY - 2016/1/1
Y1 - 2016/1/1
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 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.
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 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.
UR - http://www.scopus.com/inward/record.url?scp=84989916930&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84989916930&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-46049-9_3
DO - 10.1007/978-3-319-46049-9_3
M3 - Conference contribution
AN - SCOPUS:84989916930
SN - 9783319460482
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 22
EP - 34
BT - String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings
A2 - Inenaga, Shunsuke
A2 - Sadakane, Kunihiko
A2 - Sakai, Tetsuya
PB - Springer Verlag
T2 - 23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016
Y2 - 18 October 2016 through 20 October 2016
ER -