On Maximal Unbordered Factors

Gregory Kucherov; Alexander Loptev; Tatiana Starikovskaya

doi:10.1007/978-3-319-19929-0_29

On Maximal Unbordered Factors

Gregory Kucherov, Alexander Loptev, Tatiana Starikovskaya

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

6 Citations (Scopus)

219 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 language	English
Title of host publication	Combinatorial Pattern Matching
Subtitle of host publication	26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings
Publisher	Springer International Publishing AG
Pages	343-354
Number of pages	12
ISBN (Electronic)	9783319199290
ISBN (Print)	9783319199283
DOIs	https://doi.org/10.1007/978-3-319-19929-0_29
Publication status	Published - 16 Jun 2015

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer International Publishing
Volume	9133
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-319-19929-0_29

1504.07406v1
The final version is available from Springer at: http://dx.doi.org/10.1007/978-3-319-19929-0_29
Accepted author manuscript, 362 KB

Handle.net

Persistent link

Cite this

@inproceedings{119f2fc2916f4ddd83626030d6641b36,

title = "On Maximal Unbordered Factors",

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.",

author = "Gregory Kucherov and Alexander Loptev and Tatiana Starikovskaya",

year = "2015",

month = jun,

day = "16",

doi = "10.1007/978-3-319-19929-0_29",

language = "English",

isbn = "9783319199283",

series = "Lecture Notes in Computer Science",

publisher = "Springer International Publishing AG",

pages = "343--354",

booktitle = "Combinatorial Pattern Matching",

address = "Switzerland",

}

On Maximal Unbordered Factors. / Kucherov, Gregory; Loptev, Alexander; Starikovskaya, Tatiana.
Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings. Springer International Publishing AG, 2015. p. 343-354 (Lecture Notes in Computer Science; Vol. 9133).

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

TY - GEN

T1 - On Maximal Unbordered Factors

AU - Kucherov, Gregory

AU - Loptev, Alexander

AU - Starikovskaya, Tatiana

PY - 2015/6/16

Y1 - 2015/6/16

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-19929-0_29

DO - 10.1007/978-3-319-19929-0_29

M3 - Conference Contribution (Conference Proceeding)

SN - 9783319199283

T3 - Lecture Notes in Computer Science

SP - 343

EP - 354

BT - Combinatorial Pattern Matching

PB - Springer International Publishing AG

ER -

On Maximal Unbordered Factors

Abstract

Publication series

Access to Document

Handle.net

Fingerprint

Cite this