Cover array string reconstruction

Maxime Crochemore; Costas S. Iliopoulos; Solon Pissis; German Tischler

doi:10.1007/978-3-642-13509-5_23

Cover array string reconstruction

Maxime Crochemore, Costas S. Iliopoulos, Solon Pissis, German Tischler

Informatics

King's College London

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

32 Citations (Scopus)

Abstract

A proper factor u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimal-cover (resp. maximal-cover) array of y if C[i] is the minimal (resp. maximal) length of covers of y[0..i,], or zero if no cover exists.In this paper, we present a constructive algorithm checking the validity of an array as a minimal-cover or maximal-cover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. All algorithms run in linear time due to an interesting combinatorial property of cover arrays: the sum of important values in a cover array is bounded by twice the length of the string.

Original language	English
Title of host publication	Combinatorial Pattern Matching
Subtitle of host publication	21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010. Proceedings
Editors	Amihood Amir, Laxmi Panda
Place of Publication	Berlin ; New York
Publisher	Springer Berlin Heidelberg
Pages	251 - 259
Number of pages	9
Volume	N/A
Edition	N/A
ISBN (Print)	9783642135088
DOIs	https://doi.org/10.1007/978-3-642-13509-5_23
Publication status	Published - 2010
Event	21st Annual Symposium on Combinatorial Pattern Matching - Brooklyn, NY Duration: 21 Jun 2010 → 23 Jun 2010

Publication series

Name	Lecture Notes in Computer Science
Volume	6129
ISSN (Electronic)	0302-9743

Conference

Conference	21st Annual Symposium on Combinatorial Pattern Matching
City	Brooklyn, NY
Period	21/06/2010 → 23/06/2010

Access to Document

10.1007/978-3-642-13509-5_23

Cite this

Crochemore, M., Iliopoulos, C. S., Pissis, S., & Tischler, G. (2010). Cover array string reconstruction. In A. Amir, & L. Panda (Eds.), Combinatorial Pattern Matching: 21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010. Proceedings (N/A ed., Vol. N/A, pp. 251 - 259). (Lecture Notes in Computer Science; Vol. 6129). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-13509-5_23

Crochemore, Maxime ; Iliopoulos, Costas S. ; Pissis, Solon et al. / Cover array string reconstruction. Combinatorial Pattern Matching: 21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010. Proceedings. editor / Amihood Amir ; Laxmi Panda. Vol. N/A N/A. ed. Berlin ; New York : Springer Berlin Heidelberg, 2010. pp. 251 - 259 (Lecture Notes in Computer Science).

@inbook{852dfc403b484474907b6db4fb687015,

title = "Cover array string reconstruction",

abstract = "A proper factor u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimal-cover (resp. maximal-cover) array of y if C[i] is the minimal (resp. maximal) length of covers of y[0..i,], or zero if no cover exists.In this paper, we present a constructive algorithm checking the validity of an array as a minimal-cover or maximal-cover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. All algorithms run in linear time due to an interesting combinatorial property of cover arrays: the sum of important values in a cover array is bounded by twice the length of the string.",

author = "Maxime Crochemore and Iliopoulos, {Costas S.} and Solon Pissis and German Tischler",

year = "2010",

doi = "10.1007/978-3-642-13509-5_23",

language = "English",

isbn = "9783642135088",

volume = "N/A",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "251 -- 259",

editor = "Amihood Amir and Laxmi Panda",

booktitle = "Combinatorial Pattern Matching",

edition = "N/A",

note = "21st Annual Symposium on Combinatorial Pattern Matching ; Conference date: 21-06-2010 Through 23-06-2010",

}

Crochemore, M , Iliopoulos, CS , Pissis, S & Tischler, G 2010, Cover array string reconstruction. in A Amir & L Panda (eds), Combinatorial Pattern Matching: 21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010. Proceedings. N/A edn, vol. N/A, Lecture Notes in Computer Science, vol. 6129, Springer Berlin Heidelberg, Berlin ; New York, pp. 251 - 259, 21st Annual Symposium on Combinatorial Pattern Matching, Brooklyn, NY, 21/06/2010. https://doi.org/10.1007/978-3-642-13509-5_23

Cover array string reconstruction. / Crochemore, Maxime ; Iliopoulos, Costas S.; Pissis, Solon et al.
Combinatorial Pattern Matching: 21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010. Proceedings. ed. / Amihood Amir; Laxmi Panda. Vol. N/A N/A. ed. Berlin ; New York: Springer Berlin Heidelberg, 2010. p. 251 - 259 (Lecture Notes in Computer Science; Vol. 6129).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

TY - CHAP

T1 - Cover array string reconstruction

AU - Crochemore, Maxime

AU - Iliopoulos, Costas S.

AU - Pissis, Solon

AU - Tischler, German

PY - 2010

Y1 - 2010

N2 - A proper factor u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimal-cover (resp. maximal-cover) array of y if C[i] is the minimal (resp. maximal) length of covers of y[0..i,], or zero if no cover exists.In this paper, we present a constructive algorithm checking the validity of an array as a minimal-cover or maximal-cover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. All algorithms run in linear time due to an interesting combinatorial property of cover arrays: the sum of important values in a cover array is bounded by twice the length of the string.

AB - A proper factor u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimal-cover (resp. maximal-cover) array of y if C[i] is the minimal (resp. maximal) length of covers of y[0..i,], or zero if no cover exists.In this paper, we present a constructive algorithm checking the validity of an array as a minimal-cover or maximal-cover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. All algorithms run in linear time due to an interesting combinatorial property of cover arrays: the sum of important values in a cover array is bounded by twice the length of the string.

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

U2 - 10.1007/978-3-642-13509-5_23

DO - 10.1007/978-3-642-13509-5_23

M3 - Conference paper

SN - 9783642135088

VL - N/A

T3 - Lecture Notes in Computer Science

SP - 251

EP - 259

BT - Combinatorial Pattern Matching

A2 - Amir, Amihood

A2 - Panda, Laxmi

PB - Springer Berlin Heidelberg

CY - Berlin ; New York

T2 - 21st Annual Symposium on Combinatorial Pattern Matching

Y2 - 21 June 2010 through 23 June 2010

ER -

Crochemore M , Iliopoulos CS , Pissis S, Tischler G. Cover array string reconstruction. In Amir A, Panda L, editors, Combinatorial Pattern Matching: 21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010. Proceedings. N/A ed. Vol. N/A. Berlin ; New York: Springer Berlin Heidelberg. 2010. p. 251 - 259. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-13509-5_23

Cover array string reconstruction

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this