Maximal unbordered factors of random strings

Patrick Hagge Cording, Mathias Bæk Tejs Knudsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of the 23rd International Symposium String Processing and Information Retrieval (SPIRE 2016)
EditorsShunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
PublisherSpringer
Publication date2016
Pages93-96
ISBN (Print) 978-3-319-46048-2
ISBN (Electronic)978-3-319-46049-9
DOIs
Publication statusPublished - 2016
Event23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016) - Beppu, Japan
Duration: 18 Oct 201620 Oct 2016
Conference number: 23
https://sites.google.com/site/spire2016jp/

Conference

Conference23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016)
Number23
CountryJapan
CityBeppu
Period18/10/201620/10/2016
Internet address
SeriesLecture Notes in Computer Science
Volume9954
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Maximal unbordered factors of random strings'. Together they form a unique fingerprint.

Cite this