Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Ellert, Jonas; Fischer, Johannes https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-141322
URL:

;

Linear Time Runs Over General Ordered Alphabets

pdf-format:


Abstract

A run in a string is a maximal periodic substring. For example, the string bananatree contains the runs anana = (an)^{5/2} and ee = e². There are less than n runs in any length-n string, and computing all runs for a string over a linearly-sortable alphabet takes 𝒪(n) time (Bannai et al., SIAM J. Comput. 2017). Kosolobov conjectured that there also exists a linear time runs algorithm for general ordered alphabets (Inf. Process. Lett. 2016). The conjecture was almost proven by Crochemore et al., who presented an 𝒪(nα(n)) time algorithm (where α(n) is the extremely slowly growing inverse Ackermann function). We show how to achieve 𝒪(n) time by exploiting combinatorial properties of the Lyndon array, thus proving Kosolobov’s conjecture. This also positively answers the at least 29-year-old question whether square-freeness can be tested in linear time over general ordered alphabets (Breslauer, PhD thesis, Columbia University 1992).

BibTeX - Entry

@InProceedings{ellert_et_al:LIPIcs.ICALP.2021.63,
  author =	{Ellert, Jonas and Fischer, Johannes},
  title =	{{Linear Time Runs Over General Ordered Alphabets}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{63:1--63:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14132},
  URN =		{urn:nbn:de:0030-drops-141322},
  doi =		{10.4230/LIPIcs.ICALP.2021.63},
  annote =	{Keywords: String algorithms, Lyndon array, runs, squares, longest common extension, general ordered alphabets, combinatorics on words}
}

Keywords: String algorithms, Lyndon array, runs, squares, longest common extension, general ordered alphabets, combinatorics on words
Seminar: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue date: 2021
Date of publication: 02.07.2021
Supplementary Material: Software (Source Code): https://github.com/jonas-ellert/linear-time-runs/ archived at: https://archive.softwareheritage.org/swh:1:snp:aa7b1dc6293d939b5ec6e554d3102b15a518b7e7


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI