Fast algorithm for partial covers in words

Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A word w covered by u thus generalizes the idea of a repetition, that is, a word composed of exact concatenations of u. In this article we introduce a new notion of partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least a given number of positions in w. Our main result is an O(nlogn)-time algorithm for computing the shortest partial covers of a word of length n.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings
Number of pages12
Publication statusPublished - 24 Sept 2013
Externally publishedYes
Event24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013 - Bad Herrenalb, Germany
Duration: 17 Jun 201319 Jun 2013

Publication series

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


Conference24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013
CityBad Herrenalb


Dive into the research topics of 'Fast algorithm for partial covers in words'. Together they form a unique fingerprint.

Cite this