Longest unbordered factor in quasilinear time

Tomasz Kociumaka, Ritu Kundu, Manal Mohamed, Solon P. Pissis

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 log2 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(n1.5) time for integer alphabets [Gawrychowski et al., 2015].

Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation, ISAAC 2018
EditorsChung-Shou Liao, Wen-Lian Hsu, Der-Tsai Lee
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages70:1-70:13
ISBN (Electronic)9783959770941
DOIs
Publication statusPublished - 1 Dec 2018
Externally publishedYes
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan, Province of China
Duration: 16 Dec 201819 Dec 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume123
ISSN (Print)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CountryTaiwan, Province of China
CityJiaoxi, Yilan
Period16/12/1819/12/18

Keywords

  • Border
  • Factorisation
  • Longest unbordered factor
  • Period
  • Strings

Cite this