Maximal unbordered factors of random strings

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

  • Patrick Hagge Cording
  • Mathias Bæk Tejs Knudsen

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.

OriginalsprogEngelsk
TitelString Processing and Information Retrieval : 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings
RedaktørerShunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
Antal sider4
ForlagSpringer
Publikationsdato2016
Sider93-96
ISBN (Trykt)978-3-319-46048-2
ISBN (Elektronisk)978-3-319-46049-9
DOI
StatusUdgivet - 2016
Begivenhed23rd International Symposium on String Processing and Information Retrieval - Beppu, Japan
Varighed: 8 okt. 201620 okt. 2016
Konferencens nummer: 23

Konference

Konference23rd International Symposium on String Processing and Information Retrieval
Nummer23
LandJapan
ByBeppu
Periode08/10/201620/10/2016
NavnLecture notes in computer science
Vol/bind9954
ISSN0302-9743

ID: 172140283