Maximal unbordered factors of random strings
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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 language | English |
|---|---|
| Title of host publication | String Processing and Information Retrieval : 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings |
| Editors | Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai |
| Number of pages | 4 |
| Publisher | Springer |
| Publication date | 2016 |
| Pages | 93-96 |
| ISBN (Print) | 978-3-319-46048-2 |
| ISBN (Electronic) | 978-3-319-46049-9 |
| DOIs | |
| Publication status | Published - 2016 |
| Event | 23rd International Symposium on String Processing and Information Retrieval - Beppu, Japan Duration: 8 Oct 2016 → 20 Oct 2016 Conference number: 23 |
Conference
| Conference | 23rd International Symposium on String Processing and Information Retrieval |
|---|---|
| Nummer | 23 |
| Land | Japan |
| By | Beppu |
| Periode | 08/10/2016 → 20/10/2016 |
| Series | Lecture notes in computer science |
|---|---|
| Volume | 9954 |
| ISSN | 0302-9743 |
ID: 172140283