Shortest covers of all cyclic shifts of a string

Maxime Crochemore; Costas S. Iliopoulos; Jakub Radoszewski; Wojciech Rytter; Juliusz Straszyński; Tomasz Waleń; Wiktor Zuba

doi:10.1007/978-3-030-39881-1_7

Shortest covers of all cyclic shifts of a string

Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

3 Citations (Scopus)

237 Downloads (Pure)

Abstract

A factor W of a string X is called a cover of X, if X can be constructed by concatenations and superpositions of W. Breslauer (IPL, 1992) proposed a well-known O(n)-time algorithm that computes the shortest cover of every prefix of a string of length n. We show an O(n log n)-time algorithm that computes the shortest cover of every cyclic shift of a string and an O(n)-time algorithm that computes the shortest among these covers. A related problem is the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is Ω(log n).

Original language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings
Editors	M. Sohel Rahman, Kunihiko Sadakane, Wing-Kin Sung
Publisher	SPRINGER
Pages	69-80
Number of pages	12
ISBN (Print)	9783030398804
DOIs	https://doi.org/10.1007/978-3-030-39881-1_7
Publication status	Published - 20 Feb 2020
Event	14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020 - Singapore, Singapore Duration: 31 Mar 2020 → 2 Apr 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12049 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020
Country/Territory	Singapore
City	Singapore
Period	31/03/2020 → 2/04/2020

Access to Document

10.1007/978-3-030-39881-1_7

Shortest covers of all_CROCHEMORE_Accepted31Oct2019_Published20Feb2020_GREEN AAMAccepted author manuscript, 334 KB

Cite this

Crochemore, M., Iliopoulos, C. S., Radoszewski, J., Rytter, W., Straszyński, J., Waleń, T., & Zuba, W. (2020). Shortest covers of all cyclic shifts of a string. In M. S. Rahman, K. Sadakane, & W.-K. Sung (Eds.), WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings (pp. 69-80). Article 69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12049 LNCS). SPRINGER. https://doi.org/10.1007/978-3-030-39881-1_7

Crochemore, Maxime ; Iliopoulos, Costas S. ; Radoszewski, Jakub et al. / Shortest covers of all cyclic shifts of a string. WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings. editor / M. Sohel Rahman ; Kunihiko Sadakane ; Wing-Kin Sung. SPRINGER, 2020. pp. 69-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{17a7934e9f8946dc849a736c1e9b26c0,

title = "Shortest covers of all cyclic shifts of a string",

abstract = "A factor W of a string X is called a cover of X, if X can be constructed by concatenations and superpositions of W. Breslauer (IPL, 1992) proposed a well-known O(n)-time algorithm that computes the shortest cover of every prefix of a string of length n. We show an O(n log n)-time algorithm that computes the shortest cover of every cyclic shift of a string and an O(n)-time algorithm that computes the shortest among these covers. A related problem is the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is Ω(log n).",

author = "Maxime Crochemore and Iliopoulos, {Costas S.} and Jakub Radoszewski and Wojciech Rytter and Juliusz Straszy{\'n}ski and Tomasz Wale{\'n} and Wiktor Zuba",

year = "2020",

month = feb,

day = "20",

doi = "10.1007/978-3-030-39881-1_7",

language = "English",

isbn = "9783030398804",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "SPRINGER",

pages = "69--80",

editor = "Rahman, {M. Sohel} and Kunihiko Sadakane and Wing-Kin Sung",

booktitle = "WALCOM",

note = "14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020 ; Conference date: 31-03-2020 Through 02-04-2020",

}

Crochemore, M , Iliopoulos, CS, Radoszewski, J, Rytter, W, Straszyński, J, Waleń, T & Zuba, W 2020, Shortest covers of all cyclic shifts of a string. in MS Rahman, K Sadakane & W-K Sung (eds), WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings., 69, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12049 LNCS, SPRINGER, pp. 69-80, 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020, Singapore, Singapore, 31/03/2020. https://doi.org/10.1007/978-3-030-39881-1_7

Shortest covers of all cyclic shifts of a string. / Crochemore, Maxime ; Iliopoulos, Costas S.; Radoszewski, Jakub et al.
WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings. ed. / M. Sohel Rahman; Kunihiko Sadakane; Wing-Kin Sung. SPRINGER, 2020. p. 69-80 69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12049 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

TY - CHAP

T1 - Shortest covers of all cyclic shifts of a string

AU - Crochemore, Maxime

AU - Iliopoulos, Costas S.

AU - Radoszewski, Jakub

AU - Rytter, Wojciech

AU - Straszyński, Juliusz

AU - Waleń, Tomasz

AU - Zuba, Wiktor

PY - 2020/2/20

Y1 - 2020/2/20

N2 - A factor W of a string X is called a cover of X, if X can be constructed by concatenations and superpositions of W. Breslauer (IPL, 1992) proposed a well-known O(n)-time algorithm that computes the shortest cover of every prefix of a string of length n. We show an O(n log n)-time algorithm that computes the shortest cover of every cyclic shift of a string and an O(n)-time algorithm that computes the shortest among these covers. A related problem is the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is Ω(log n).

AB - A factor W of a string X is called a cover of X, if X can be constructed by concatenations and superpositions of W. Breslauer (IPL, 1992) proposed a well-known O(n)-time algorithm that computes the shortest cover of every prefix of a string of length n. We show an O(n log n)-time algorithm that computes the shortest cover of every cyclic shift of a string and an O(n)-time algorithm that computes the shortest among these covers. A related problem is the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is Ω(log n).

U2 - 10.1007/978-3-030-39881-1_7

DO - 10.1007/978-3-030-39881-1_7

M3 - Conference paper

AN - SCOPUS:85080956644

SN - 9783030398804

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 69

EP - 80

BT - WALCOM

A2 - Rahman, M. Sohel

A2 - Sadakane, Kunihiko

A2 - Sung, Wing-Kin

PB - SPRINGER

T2 - 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020

Y2 - 31 March 2020 through 2 April 2020

ER -

Crochemore M , Iliopoulos CS, Radoszewski J, Rytter W, Straszyński J, Waleń T et al. Shortest covers of all cyclic shifts of a string. In Rahman MS, Sadakane K, Sung WK, editors, WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings. SPRINGER. 2020. p. 69-80. 69. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-39881-1_7

Shortest covers of all cyclic shifts of a string

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this