Periods in strings

Leo J. Guibas, Andrew M. Odlyzko

Research output: Contribution to journalArticle

115 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 nlogn. By using generating function methods we enumerate the strings having a given correlation, and investigate certain related questions.

Original languageEnglish (US)
Pages (from-to)19-42
Number of pages24
JournalJournal of Combinatorial Theory, Series A
Volume30
Issue number1
DOIs
StatePublished - Jan 1981

Fingerprint Dive into the research topics of 'Periods in strings'. Together they form a unique fingerprint.

Cite this