Optimal computation of all repetitions in a weighted string

Carl Barton; Solon Pissis

Optimal computation of all repetitions in a weighted string

Carl Barton, Solon Pissis

Informatics

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

3 Citations (Scopus)

Abstract

A repetition in a string of letters consists of exact concatenations of identical
factors of the string. Crochemore’s repetitions algorithm, usually also referred
to as Crochemore’s partitioning algorithm, was introduced in 1981, and was the
first optimal O(n log n)-time algorithm to compute all repetitions in a string of
length n. A weighted string is a string in which a set of letters may occur at each
position with respective probabilities of occurrence. In this article, we present a
new variant of Crochemore’s partitioning algorithm for weighted strings, which
requires optimal time O(n log n), thus improving on the best known O(n2)-time
algorithm for computing all repetitions in a weighted string of length n.

Original language	English
Title of host publication	Proceedings of the 2nd International Conference on Algorithms for Big Data
Editors	Costas S Iliopoulos, Alessio Langiu
Publisher	King's College London
Pages	9-15
Number of pages	7
Publication status	Published - 16 Apr 2014
Event	2nd International Conference on Algorithms for Big Data - Italy, Palermo, United Kingdom Duration: 7 Apr 2014 → 9 Apr 2014

Publication series

Name	CEUR Workshops Proceedings
ISSN (Electronic)	1613-0073

Conference

Conference	2nd International Conference on Algorithms for Big Data
Country/Territory	United Kingdom
City	Palermo
Period	7/04/2014 → 9/04/2014

Access to Document

http://ceur-ws.org/Vol-1146/

Cite this

@inbook{bda930c3f4414ae7890a4fea1ee8de05,

title = "Optimal computation of all repetitions in a weighted string",

abstract = "A repetition in a string of letters consists of exact concatenations of identicalfactors of the string. Crochemore{\textquoteright}s repetitions algorithm, usually also referredto as Crochemore{\textquoteright}s partitioning algorithm, was introduced in 1981, and was thefirst optimal O(n log n)-time algorithm to compute all repetitions in a string oflength n. A weighted string is a string in which a set of letters may occur at eachposition with respective probabilities of occurrence. In this article, we present anew variant of Crochemore{\textquoteright}s partitioning algorithm for weighted strings, whichrequires optimal time O(n log n), thus improving on the best known O(n2)-timealgorithm for computing all repetitions in a weighted string of length n.",

author = "Carl Barton and Solon Pissis",

year = "2014",

month = apr,

day = "16",

language = "English",

series = "CEUR Workshops Proceedings",

publisher = "King's College London",

pages = "9--15",

editor = "Iliopoulos, {Costas S} and Alessio Langiu",

booktitle = "Proceedings of the 2nd International Conference on Algorithms for Big Data",

note = "2nd International Conference on Algorithms for Big Data ; Conference date: 07-04-2014 Through 09-04-2014",

}

Barton, C & Pissis, S 2014, Optimal computation of all repetitions in a weighted string. in CS Iliopoulos & A Langiu (eds), Proceedings of the 2nd International Conference on Algorithms for Big Data. CEUR Workshops Proceedings, King's College London, pp. 9-15, 2nd International Conference on Algorithms for Big Data , Palermo, United Kingdom, 7/04/2014. <http://ceur-ws.org/Vol-1146/>

TY - CHAP

T1 - Optimal computation of all repetitions in a weighted string

AU - Barton, Carl

AU - Pissis, Solon

PY - 2014/4/16

Y1 - 2014/4/16

N2 - A repetition in a string of letters consists of exact concatenations of identicalfactors of the string. Crochemore’s repetitions algorithm, usually also referredto as Crochemore’s partitioning algorithm, was introduced in 1981, and was thefirst optimal O(n log n)-time algorithm to compute all repetitions in a string oflength n. A weighted string is a string in which a set of letters may occur at eachposition with respective probabilities of occurrence. In this article, we present anew variant of Crochemore’s partitioning algorithm for weighted strings, whichrequires optimal time O(n log n), thus improving on the best known O(n2)-timealgorithm for computing all repetitions in a weighted string of length n.

AB - A repetition in a string of letters consists of exact concatenations of identicalfactors of the string. Crochemore’s repetitions algorithm, usually also referredto as Crochemore’s partitioning algorithm, was introduced in 1981, and was thefirst optimal O(n log n)-time algorithm to compute all repetitions in a string oflength n. A weighted string is a string in which a set of letters may occur at eachposition with respective probabilities of occurrence. In this article, we present anew variant of Crochemore’s partitioning algorithm for weighted strings, whichrequires optimal time O(n log n), thus improving on the best known O(n2)-timealgorithm for computing all repetitions in a weighted string of length n.

M3 - Conference paper

T3 - CEUR Workshops Proceedings

SP - 9

EP - 15

BT - Proceedings of the 2nd International Conference on Algorithms for Big Data

A2 - Iliopoulos, Costas S

A2 - Langiu, Alessio

PB - King's College London

T2 - 2nd International Conference on Algorithms for Big Data

Y2 - 7 April 2014 through 9 April 2014

ER -

Optimal computation of all repetitions in a weighted string

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this