DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.70

Longest Unbordered Factor in Quasilinear Time

Authors: Tomasz Kociumaka, Ritu Kundu, Manal Mohamed, and Solon P. Pissis

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

A border u of a word w is a proper factor of w occurring both as a prefix and as a suffix. The maximal unbordered factor of w is the longest factor of w which does not have a border. Here an O(n log n)-time with high probability (or O(n log n log^2 log n)-time deterministic) algorithm to compute the Longest Unbordered Factor Array of w for general alphabets is presented, where n is the length of w. This array specifies the length of the maximal unbordered factor starting at each position of w. This is a major improvement on the running time of the currently best worst-case algorithm working in O(n^{1.5}) time for integer alphabets [Gawrychowski et al., 2015].

Cite as

Tomasz Kociumaka, Ritu Kundu, Manal Mohamed, and Solon P. Pissis. Longest Unbordered Factor in Quasilinear Time. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kociumaka_et_al:LIPIcs.ISAAC.2018.70,
  author =	{Kociumaka, Tomasz and Kundu, Ritu and Mohamed, Manal and Pissis, Solon P.},
  title =	{{Longest Unbordered Factor in Quasilinear Time}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{70:1--70:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.70},
  URN =		{urn:nbn:de:0030-drops-100184},
  doi =		{10.4230/LIPIcs.ISAAC.2018.70},
  annote =	{Keywords: longest unbordered factor, factorisation, period, border, strings}
}

Search Results

Documents authored by Kundu, Ritu

Longest Unbordered Factor in Quasilinear Time

Abstract

Cite as

Thanks for your feedback!

Could not send message