Maximal unbordered factors of random strings

Patrick Hagge Cording*, Travis Gagie, Mathias Bæk Tejs Knudsen, Tomasz Kociumaka

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border other than itself. Loptev, Kucherov, and Starikovskaya [CPM'15] conjectured the following: If we pick a string of length n from a fixed non-unary alphabet uniformly at random, then the expected maximum length of its unbordered factors is n−O(1). We confirm this conjecture by proving that the expected value is, in fact, n−O(σ−1), where σ is the size of the alphabet. This immediately implies that we can find such a maximal unbordered factor in linear time on average. However, we go further and show that the optimum average-case running time is in Ω(n)∩O(nlogσ⁡n) due to analogous bounds by Czumaj and Gąsieniec [CPM'00] for the problem of computing the shortest period of a uniformly random string.
Original languageEnglish
JournalTheoretical Computer Science
Volume852
Pages (from-to)78-83
ISSN0304-3975
DOIs
Publication statusPublished - 2020

Keywords

  • Combinatorics on strings
  • Borders
  • Unbordered factors

Fingerprint

Dive into the research topics of 'Maximal unbordered factors of random strings'. Together they form a unique fingerprint.

Cite this