On the right-seed array of a string

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

doi:10.1007/978-3-642-22685-4_43

On the right-seed array of a string

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

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We consider the problem of finding the repetitive structure of a given fixed string y. A factor u of y is a cover of y, if every letter of y falls within some occurrence of u in y. A factor v of y is a seed of y, if it is a cover of a superstring of y. There exist linear-time algorithms for solving the minimal cover problem. The minimal seed problem is of much higher algorithmic difficulty, and no linear-time algorithm is known. In this article, we solve one of its variants - computing the minimal and maximal right-seed array of a given string. A right seed of y is the shortest suffix of y that it is a cover of a superstring of y. An integer array RS is the minimal right-seed (resp. maximal right-seed) array of y, if RS[i] is the minimal (resp. maximal) length of right seeds of y[0..i]. We present an O(n log n) time algorithm that computes the minimal right-seed array of a given string, and a linear-time solution to compute the maximal right-seed array by detecting border-free prefixes of the given string.

Original language	English
Title of host publication	Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings
Pages	492-502
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-22685-4_43
Publication status	Published - 29 Aug 2011
Externally published	Yes
Event	17th Annual International Computing and Combinatorics Conference, COCOON 2011 - Dallas, TX, United States Duration: 14 Aug 2011 → 16 Aug 2011

Publication series

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

Conference

Conference	17th Annual International Computing and Combinatorics Conference, COCOON 2011
Country	United States
City	Dallas, TX
Period	14/08/11 → 16/08/11

Keywords

algorithms on strings
covers
periodicity
seeds

Access to Document

10.1007/978-3-642-22685-4_43

Cite this

Christou, M., Crochemore, M., Guth, O., Iliopoulos, C. S., & Pissis, S. P. (2011). On the right-seed array of a string. In Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings (pp. 492-502). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6842 LNCS). https://doi.org/10.1007/978-3-642-22685-4_43

Christou, Michalis ; Crochemore, Maxime ; Guth, Ondrej ; Iliopoulos, Costas S. ; Pissis, Solon P. / On the right-seed array of a string. Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings. 2011. pp. 492-502 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{497c343fb6024e6f86180abfb560c930,

title = "On the right-seed array of a string",

abstract = "We consider the problem of finding the repetitive structure of a given fixed string y. A factor u of y is a cover of y, if every letter of y falls within some occurrence of u in y. A factor v of y is a seed of y, if it is a cover of a superstring of y. There exist linear-time algorithms for solving the minimal cover problem. The minimal seed problem is of much higher algorithmic difficulty, and no linear-time algorithm is known. In this article, we solve one of its variants - computing the minimal and maximal right-seed array of a given string. A right seed of y is the shortest suffix of y that it is a cover of a superstring of y. An integer array RS is the minimal right-seed (resp. maximal right-seed) array of y, if RS[i] is the minimal (resp. maximal) length of right seeds of y[0..i]. We present an O(n log n) time algorithm that computes the minimal right-seed array of a given string, and a linear-time solution to compute the maximal right-seed array by detecting border-free prefixes of the given string.",

keywords = "algorithms on strings, covers, periodicity, seeds",

author = "Michalis Christou and Maxime Crochemore and Ondrej Guth and Iliopoulos, {Costas S.} and Pissis, {Solon P.}",

year = "2011",

month = aug,

day = "29",

doi = "10.1007/978-3-642-22685-4_43",

language = "English",

isbn = "9783642226847",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "492--502",

booktitle = "Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings",

note = "17th Annual International Computing and Combinatorics Conference, COCOON 2011 ; Conference date: 14-08-2011 Through 16-08-2011",

}

Christou, M, Crochemore, M, Guth, O, Iliopoulos, CS & Pissis, SP 2011, On the right-seed array of a string. in Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6842 LNCS, pp. 492-502, 17th Annual International Computing and Combinatorics Conference, COCOON 2011, Dallas, TX, United States, 14/08/11. https://doi.org/10.1007/978-3-642-22685-4_43

On the right-seed array of a string. / Christou, Michalis; Crochemore, Maxime; Guth, Ondrej; Iliopoulos, Costas S.; Pissis, Solon P.

Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings. 2011. p. 492-502 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6842 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the right-seed array of a string

AU - Christou, Michalis

AU - Crochemore, Maxime

AU - Guth, Ondrej

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

PY - 2011/8/29

Y1 - 2011/8/29

N2 - We consider the problem of finding the repetitive structure of a given fixed string y. A factor u of y is a cover of y, if every letter of y falls within some occurrence of u in y. A factor v of y is a seed of y, if it is a cover of a superstring of y. There exist linear-time algorithms for solving the minimal cover problem. The minimal seed problem is of much higher algorithmic difficulty, and no linear-time algorithm is known. In this article, we solve one of its variants - computing the minimal and maximal right-seed array of a given string. A right seed of y is the shortest suffix of y that it is a cover of a superstring of y. An integer array RS is the minimal right-seed (resp. maximal right-seed) array of y, if RS[i] is the minimal (resp. maximal) length of right seeds of y[0..i]. We present an O(n log n) time algorithm that computes the minimal right-seed array of a given string, and a linear-time solution to compute the maximal right-seed array by detecting border-free prefixes of the given string.

AB - We consider the problem of finding the repetitive structure of a given fixed string y. A factor u of y is a cover of y, if every letter of y falls within some occurrence of u in y. A factor v of y is a seed of y, if it is a cover of a superstring of y. There exist linear-time algorithms for solving the minimal cover problem. The minimal seed problem is of much higher algorithmic difficulty, and no linear-time algorithm is known. In this article, we solve one of its variants - computing the minimal and maximal right-seed array of a given string. A right seed of y is the shortest suffix of y that it is a cover of a superstring of y. An integer array RS is the minimal right-seed (resp. maximal right-seed) array of y, if RS[i] is the minimal (resp. maximal) length of right seeds of y[0..i]. We present an O(n log n) time algorithm that computes the minimal right-seed array of a given string, and a linear-time solution to compute the maximal right-seed array by detecting border-free prefixes of the given string.

KW - algorithms on strings

KW - covers

KW - periodicity

KW - seeds

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

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

U2 - 10.1007/978-3-642-22685-4_43

DO - 10.1007/978-3-642-22685-4_43

M3 - Conference contribution

AN - SCOPUS:80051994885

SN - 9783642226847

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 492

EP - 502

BT - Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings

T2 - 17th Annual International Computing and Combinatorics Conference, COCOON 2011

Y2 - 14 August 2011 through 16 August 2011

ER -

Christou M, Crochemore M, Guth O, Iliopoulos CS, Pissis SP. On the right-seed array of a string. In Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings. 2011. p. 492-502. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-22685-4_43

On the right-seed array of a string

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this