TY - JOUR

T1 - On left and right seeds of a string

AU - Christou, Michalis

AU - Crochemore, Maxime

AU - Guth, Ondrej

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

PY - 2012/12/1

Y1 - 2012/12/1

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

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

KW - Periodicity

KW - Quasiperiodicity

KW - Seeds

UR - http://www.scopus.com/inward/record.url?scp=84871435588&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84871435588&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2012.10.004

DO - 10.1016/j.jda.2012.10.004

M3 - Article

AN - SCOPUS:84871435588

SN - 1570-8667

VL - 17

SP - 31

EP - 44

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -