On Maximal Unbordered Factors

Gregory Kucherov, Alexander Loptev, Tatiana Starikovskaya

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

5 Citations (Scopus)
213 Downloads (Pure)

Abstract

Given a string S of length n, its maximal unbordered factor is the longest factor which does not have a border. In this work we investigate the relationship between n and the length of the maximal unbordered factor of S. We prove that for the alphabet of size σ≥5 the expected length of the maximal unbordered factor of a string of length n is at least 0.99n (for sufficiently large values of n). As an application of this result, we propose a new algorithm for computing the maximal unbordered factor of a string.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
Subtitle of host publication26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings
PublisherSpringer International Publishing AG
Pages343-354
Number of pages12
ISBN (Electronic)9783319199290
ISBN (Print)9783319199283
DOIs
Publication statusPublished - 16 Jun 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume9133
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'On Maximal Unbordered Factors'. Together they form a unique fingerprint.

Cite this