On the complexity of determining the period of a string

Artur Czumaj; Leszek Gaşieniec

doi:10.1007/3-540-45123-4_34

On the complexity of determining the period of a string

Artur Czumaj, Leszek Gaşieniec

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

8 Scopus citations

Abstract

We study the complexity of a classical combinatorial problem of computing the period of a string.We investigate both the average- and the worst-case complexity of the problem. We deliver almost tight bounds for the average-case. We show that every algorithm computing the period must examine (formula presented) symbols of an input string of lengthm. On the other hand we present an algorithm that computes the period by examining on average (formula presented) symbols, where |Σ| ³ 2 stands for the input alphabet. We also present a deterministic algorithm that computes the period of a string usingm+O(m^3/4) comparisons. This is the first algorithm that have the worstcase complexity m + o(m)

Original language	English (US)
Title of host publication	Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings
Editors	Raffaele Giancarlo, David Sankoff
Publisher	Springer Verlag
Pages	412-422
Number of pages	11
ISBN (Electronic)	3540676333, 9783540676331
DOIs	https://doi.org/10.1007/3-540-45123-4_34
State	Published - Jan 1 2000
Externally published	Yes
Event	11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000 - Montreal, Canada Duration: Jun 21 2000 → Jun 23 2000

Publication series

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

Conference

Conference	11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000
Country/Territory	Canada
City	Montreal
Period	6/21/00 → 6/23/00

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-45123-4_34

Cite this

Czumaj, A., & Gaşieniec, L. (2000). On the complexity of determining the period of a string. In R. Giancarlo, & D. Sankoff (Eds.), Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings (pp. 412-422). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1848). Springer Verlag. https://doi.org/10.1007/3-540-45123-4_34

On the complexity of determining the period of a string. / Czumaj, Artur; Gaşieniec, Leszek.
Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. ed. / Raffaele Giancarlo; David Sankoff. Springer Verlag, 2000. p. 412-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1848).

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

Czumaj, A & Gaşieniec, L 2000, On the complexity of determining the period of a string. in R Giancarlo & D Sankoff (eds), Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1848, Springer Verlag, pp. 412-422, 11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000, Montreal, Canada, 6/21/00. https://doi.org/10.1007/3-540-45123-4_34

Czumaj A, Gaşieniec L. On the complexity of determining the period of a string. In Giancarlo R, Sankoff D, editors, Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. Springer Verlag. 2000. p. 412-422. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45123-4_34

Czumaj, Artur ; Gaşieniec, Leszek. / On the complexity of determining the period of a string. Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. editor / Raffaele Giancarlo ; David Sankoff. Springer Verlag, 2000. pp. 412-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1859975dffcf4f5cae8ced280e79d86e,

title = "On the complexity of determining the period of a string",

abstract = "We study the complexity of a classical combinatorial problem of computing the period of a string.We investigate both the average- and the worst-case complexity of the problem. We deliver almost tight bounds for the average-case. We show that every algorithm computing the period must examine (formula presented) symbols of an input string of lengthm. On the other hand we present an algorithm that computes the period by examining on average (formula presented) symbols, where |Σ| ³ 2 stands for the input alphabet. We also present a deterministic algorithm that computes the period of a string usingm+O(m3/4) comparisons. This is the first algorithm that have the worstcase complexity m + o(m)",

author = "Artur Czumaj and Leszek Ga{\c s}ieniec",

year = "2000",

month = jan,

day = "1",

doi = "10.1007/3-540-45123-4_34",

language = "English (US)",

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

publisher = "Springer Verlag",

pages = "412--422",

editor = "Raffaele Giancarlo and David Sankoff",

booktitle = "Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings",

note = "11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000 ; Conference date: 21-06-2000 Through 23-06-2000",

}

TY - GEN

T1 - On the complexity of determining the period of a string

AU - Czumaj, Artur

AU - Gaşieniec, Leszek

PY - 2000/1/1

Y1 - 2000/1/1

N2 - We study the complexity of a classical combinatorial problem of computing the period of a string.We investigate both the average- and the worst-case complexity of the problem. We deliver almost tight bounds for the average-case. We show that every algorithm computing the period must examine (formula presented) symbols of an input string of lengthm. On the other hand we present an algorithm that computes the period by examining on average (formula presented) symbols, where |Σ| ³ 2 stands for the input alphabet. We also present a deterministic algorithm that computes the period of a string usingm+O(m3/4) comparisons. This is the first algorithm that have the worstcase complexity m + o(m)

AB - We study the complexity of a classical combinatorial problem of computing the period of a string.We investigate both the average- and the worst-case complexity of the problem. We deliver almost tight bounds for the average-case. We show that every algorithm computing the period must examine (formula presented) symbols of an input string of lengthm. On the other hand we present an algorithm that computes the period by examining on average (formula presented) symbols, where |Σ| ³ 2 stands for the input alphabet. We also present a deterministic algorithm that computes the period of a string usingm+O(m3/4) comparisons. This is the first algorithm that have the worstcase complexity m + o(m)

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

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

U2 - 10.1007/3-540-45123-4_34

DO - 10.1007/3-540-45123-4_34

M3 - Conference contribution

AN - SCOPUS:84937432920

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

SP - 412

EP - 422

BT - Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings

A2 - Giancarlo, Raffaele

A2 - Sankoff, David

PB - Springer Verlag

T2 - 11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000

Y2 - 21 June 2000 through 23 June 2000

ER -

On the complexity of determining the period of a string

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this