Standard
Maximal unbordered factors of random strings. / Cording, Patrick Hagge; Knudsen, Mathias Bæk Tejs.
String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. ed. / Shunsuke Inenaga; Kunihiko Sadakane; Tetsuya Sakai. Springer, 2016. p. 93-96 (Lecture notes in computer science, Vol. 9954).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Cording, PH & Knudsen, MBT 2016,
Maximal unbordered factors of random strings. in S Inenaga, K Sadakane & T Sakai (eds),
String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Springer, Lecture notes in computer science, vol. 9954, pp. 93-96, 23rd International Symposium on String Processing and Information Retrieval, Beppu, Japan,
08/10/2016.
https://doi.org/10.1007/978-3-319-46049-9_9APA
Cording, P. H., & Knudsen, M. B. T. (2016).
Maximal unbordered factors of random strings. In S. Inenaga, K. Sadakane, & T. Sakai (Eds.),
String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings (pp. 93-96). Springer. Lecture notes in computer science Vol. 9954
https://doi.org/10.1007/978-3-319-46049-9_9Vancouver
Cording PH, Knudsen MBT.
Maximal unbordered factors of random strings. In Inenaga S, Sadakane K, Sakai T, editors, String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Springer. 2016. p. 93-96. (Lecture notes in computer science, Vol. 9954).
https://doi.org/10.1007/978-3-319-46049-9_9Author
Cording, Patrick Hagge ; Knudsen, Mathias Bæk Tejs. / Maximal unbordered factors of random strings. String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. editor / Shunsuke Inenaga ; Kunihiko Sadakane ; Tetsuya Sakai. Springer, 2016. pp. 93-96 (Lecture notes in computer science, Vol. 9954).
Bibtex
@inproceedings{44e57290e1e546d29d458737eff66a7e,
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. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length n from a fixed alphabet uniformly at random, then the expected length of the maximal unbordered factor is n − O(1). We prove that this conjecture is true by proving that the expected value is in fact n−Θ(σ−1), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.",
author = "Cording, {Patrick Hagge} and Knudsen, {Mathias B{\ae}k Tejs}",
year = "2016",
doi = "10.1007/978-3-319-46049-9_9",
language = "English",
isbn = "978-3-319-46048-2",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "93--96",
editor = "Shunsuke Inenaga and Kunihiko Sadakane and Tetsuya Sakai",
booktitle = "String Processing and Information Retrieval",
address = "Switzerland",
note = "null ; Conference date: 08-10-2016 Through 20-10-2016",
}
RIS
TY - GEN
T1 - Maximal unbordered factors of random strings
AU - Cording, Patrick Hagge
AU - Knudsen, Mathias Bæk Tejs
N1 - Conference code: 23
PY - 2016
Y1 - 2016
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. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length n from a fixed alphabet uniformly at random, then the expected length of the maximal unbordered factor is n − O(1). We prove that this conjecture is true by proving that the expected value is in fact n−Θ(σ−1), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.
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. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length n from a fixed alphabet uniformly at random, then the expected length of the maximal unbordered factor is n − O(1). We prove that this conjecture is true by proving that the expected value is in fact n−Θ(σ−1), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.
UR - http://www.scopus.com/inward/record.url?scp=84989815012&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-46049-9_9
DO - 10.1007/978-3-319-46049-9_9
M3 - Article in proceedings
AN - SCOPUS:84989815012
SN - 978-3-319-46048-2
T3 - Lecture notes in computer science
SP - 93
EP - 96
BT - String Processing and Information Retrieval
A2 - Inenaga, Shunsuke
A2 - Sadakane, Kunihiko
A2 - Sakai, Tetsuya
PB - Springer
Y2 - 8 October 2016 through 20 October 2016
ER -
