Fast Algorithm for Partial Covers in Words

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

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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 α positions in w. We develop a data structure of O(n) size (where n=|w|) that can be constructed in O(nlogn) time which we apply to compute all shortest α-partial covers for a given α. We also employ it for an O(nlogn)-time algorithm computing a shortest α-partial cover for each α=1,2,…,n.

Original languageEnglish
Pages (from-to)217-233
Number of pages17
JournalAlgorithmica
Volume73
Issue number1
DOIs
Publication statusPublished - 2 Sep 2015
Externally publishedYes

Keywords

  • Cover of a word
  • Quasiperiodicity
  • Suffix tree

Fingerprint

Dive into the research topics of 'Fast Algorithm for Partial Covers in Words'. Together they form a unique fingerprint.

Cite this