On left and right seeds of a string

Michalis Christou*, Maxime Crochemore, Ondrej Guth, Costas S. Iliopoulos, Solon P. Pissis

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider the problem of finding the repetitive structure of a given string y of length n. A factor u of y is a cover of y, if every letter of y lies within some occurrence of u in y. A string v is a seed of y, if it is a cover of a superstring of y. A left seed of y is a prefix of y, that is a cover of a superstring of y. Similarly, a right seed of y is a suffix of y, that is a cover of a superstring of y. An integer array LS is the minimal left-seed (resp. maximal left-seed) array of y, if LS[i] is the minimal (resp. maximal) length of left seeds of y[0.i]. The minimal right-seed (resp. maximal right-seed) array RS of y is defined in a similar fashion. In this article, we present linear-time algorithms for computing all left and right seeds of y, a linear-time algorithm for computing the minimal left-seed array of y, a linear-time solution for computing the maximal left-seed array of y, an O(nlogn)-time algorithm for computing the minimal right-seed array of y, and a linear-time solution for computing the maximal right-seed array of y. All algorithms use linear auxiliary space.

Original languageEnglish
Pages (from-to)31-44
Number of pages14
JournalJournal of Discrete Algorithms
Volume17
DOIs
Publication statusPublished - 1 Dec 2012
Externally publishedYes

Keywords

  • Periodicity
  • Quasiperiodicity
  • Seeds

Fingerprint Dive into the research topics of 'On left and right seeds of a string'. Together they form a unique fingerprint.

Cite this