Maximal unbordered factors of random strings
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Maximal unbordered factors of random strings. / Cording, Patrick Hagge; Gagie, Travis; Knudsen, Mathias Bæk Tejs; Kociumaka, Tomasz.
In: Theoretical Computer Science, Vol. 852, 2021, p. 78-83.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Maximal unbordered factors of random strings
AU - Cording, Patrick Hagge
AU - Gagie, Travis
AU - Knudsen, Mathias Bæk Tejs
AU - Kociumaka, Tomasz
N1 - Publisher Copyright: © 2020 Elsevier B.V.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Borders
KW - Combinatorics on strings
KW - Unbordered factors
UR - http://www.scopus.com/inward/record.url?scp=85096831237&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2020.11.019
DO - 10.1016/j.tcs.2020.11.019
M3 - Journal article
AN - SCOPUS:85096831237
VL - 852
SP - 78
EP - 83
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -
ID: 269501934