Maximal unbordered factors of random strings
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Indsendt manuskript, 169 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Theoretical Computer Science |
Vol/bind | 852 |
Sider (fra-til) | 78-83 |
Antal sider | 6 |
ISSN | 0304-3975 |
DOI | |
Status | Udgivet - 2021 |
Bibliografisk note
Funding Information:
Supported by the Danish Research Council under the Sapere Aude Program (DFF 4005-00267).Research partly supported by Mikkel Thorup's Advanced Grant from the Danish Council for Independent Research under the Sapere Aude research career programme and the FNU project AlgoDisc ? Discrete Mathematics, Algorithms, and Data Structures.Supported by ISF grants no. 1278/16, 824/17, and 1926/19, a BSF grant no. 2018364, and an ERC grant MPM (no. 683064) under the EU's Horizon 2020 Research and Innovation Programme.
Publisher Copyright:
© 2020 Elsevier B.V.
ID: 269501934