Periods in strings

Leo J. Guibas; Andrew M. Odlyzko

doi:10.1016/0097-3165(81)90038-8

Periods in strings

Leo J. Guibas
, Andrew M. Odlyzko

School of Mathematics

Research output: Contribution to journal › Article › peer-review

137 Scopus citations

Abstract

In this paper we explore the notion of periods of a string. A period can be thought of as a shift that causes the string to match over itself. We obtain two sets of necessary and sufficient conditions for a set of integers to be the set of periods of some string (what we call the correlation of the string). We show that the number of distinct correlations of length n is independent of the alphabet size and is of order n^logn. By using generating function methods we enumerate the strings having a given correlation, and investigate certain related questions.

Original language	English (US)
Pages (from-to)	19-42
Number of pages	24
Journal	Journal of Combinatorial Theory, Series A
Volume	30
Issue number	1
DOIs	https://doi.org/10.1016/0097-3165(81)90038-8
State	Published - Jan 1981

Publisher link

10.1016/0097-3165(81)90038-8

Find It

Find It at U of M Libraries

Cite this

@article{1935ca74cf8d4e6ab376e2c24c8f6442,

title = "Periods in strings",

abstract = "In this paper we explore the notion of periods of a string. A period can be thought of as a shift that causes the string to match over itself. We obtain two sets of necessary and sufficient conditions for a set of integers to be the set of periods of some string (what we call the correlation of the string). We show that the number of distinct correlations of length n is independent of the alphabet size and is of order nlogn. By using generating function methods we enumerate the strings having a given correlation, and investigate certain related questions.",

author = "Guibas, \{Leo J.\} and Odlyzko, \{Andrew M.\}",

year = "1981",

month = jan,

doi = "10.1016/0097-3165(81)90038-8",

language = "English (US)",

volume = "30",

pages = "19--42",

journal = "Journal of Combinatorial Theory, Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Periods in strings

AU - Guibas, Leo J.

AU - Odlyzko, Andrew M.

PY - 1981/1

Y1 - 1981/1

N2 - In this paper we explore the notion of periods of a string. A period can be thought of as a shift that causes the string to match over itself. We obtain two sets of necessary and sufficient conditions for a set of integers to be the set of periods of some string (what we call the correlation of the string). We show that the number of distinct correlations of length n is independent of the alphabet size and is of order nlogn. By using generating function methods we enumerate the strings having a given correlation, and investigate certain related questions.

AB - In this paper we explore the notion of periods of a string. A period can be thought of as a shift that causes the string to match over itself. We obtain two sets of necessary and sufficient conditions for a set of integers to be the set of periods of some string (what we call the correlation of the string). We show that the number of distinct correlations of length n is independent of the alphabet size and is of order nlogn. By using generating function methods we enumerate the strings having a given correlation, and investigate certain related questions.

UR - https://www.scopus.com/pages/publications/0001770019

UR - https://www.scopus.com/pages/publications/0001770019#tab=citedBy

U2 - 10.1016/0097-3165(81)90038-8

DO - 10.1016/0097-3165(81)90038-8

M3 - Article

AN - SCOPUS:0001770019

SN - 0097-3165

VL - 30

SP - 19

EP - 42

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 1

ER -

Periods in strings

Abstract

Publisher link

Find It

Other files and links

Fingerprint

Cite this