King's College London

Research portal

Shortest covers of all cyclic shifts of a string

Research output: Chapter in Book/Report/Conference proceedingConference paper

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

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings
EditorsM. Sohel Rahman, Kunihiko Sadakane, Wing-Kin Sung
PublisherSPRINGER
Pages69-80
Number of pages12
ISBN (Print)9783030398804
DOIs
Publication statusPublished - 20 Feb 2020
Event14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020 - Singapore, Singapore
Duration: 31 Mar 20202 Apr 2020

Publication series

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

Conference

Conference14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020
CountrySingapore
CitySingapore
Period31/03/20202/04/2020

Documents

King's Authors

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

Download statistics

No data available

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454