Maximal unbordered factors of random strings

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

Maximal unbordered factors of random strings. / Cording, Patrick Hagge; Gagie, Travis; Knudsen, Mathias Bæk Tejs; Kociumaka, Tomasz.

I: Theoretical Computer Science, Bind 852, 2021, s. 78-83.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Cording, PH, Gagie, T, Knudsen, MBT & Kociumaka, T 2021, 'Maximal unbordered factors of random strings', Theoretical Computer Science, bind 852, s. 78-83. https://doi.org/10.1016/j.tcs.2020.11.019

APA

Cording, P. H., Gagie, T., Knudsen, M. B. T., & Kociumaka, T. (2021). Maximal unbordered factors of random strings. Theoretical Computer Science, 852, 78-83. https://doi.org/10.1016/j.tcs.2020.11.019

Vancouver

Cording PH, Gagie T, Knudsen MBT, Kociumaka T. Maximal unbordered factors of random strings. Theoretical Computer Science. 2021;852:78-83. https://doi.org/10.1016/j.tcs.2020.11.019

Author

Cording, Patrick Hagge ; Gagie, Travis ; Knudsen, Mathias Bæk Tejs ; Kociumaka, Tomasz. / Maximal unbordered factors of random strings. I: Theoretical Computer Science. 2021 ; Bind 852. s. 78-83.

Bibtex

@article{cf3466b67e914051ae0b379f69eba267,

title = "Maximal unbordered factors of random strings",

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{\c a}sieniec [CPM'00] for the problem of computing the shortest period of a uniformly random string.",

keywords = "Borders, Combinatorics on strings, Unbordered factors",

author = "Cording, {Patrick Hagge} and Travis Gagie and Knudsen, {Mathias B{\ae}k Tejs} and Tomasz Kociumaka",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2021",

doi = "10.1016/j.tcs.2020.11.019",

language = "English",

volume = "852",

pages = "78--83",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

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

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

Datalogisk Institut