How many squares can a string contain?
type: Item
instance of: scholarly article
title: How many squares can a string contain?
zbMATH Open document ID: 0910.05001
author: Aviezri S. Fraenkel
author: Jamie Simpson
published in: Journal of Combinatorial Theory. Series A
publication date: 1998-10-18T00:00:00Z
review text: Given a word over a fixed alphabet, a square is a subword of the form \(uu= u^2\) where \(u\) is a nonempty word. Denote by \(M(n)\) the maximum number of distinct squares (not translates of each other) possible in a word of length \(n\). Given the word \(a_1a_2\cdots a_n\) let \(s_i\) be the number of squares beginning with \(a_i\) that do not appear later. The authors show \(s_i\leq 2\), \(1\leq i\leq n\), and deduce that \(M(n)< 2n\) for all \(n\). Additionally, for infinitely many \(n\) it is shown that \(M(n)= n- o(n)\). Similar results are obtained for \(P(n)\), the maximum number of distinct primitive squares (\(u\) is not of the form \(v^j\), \(j\geq 2\)) possible in a word of length \(n\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 11B75
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 1212932
zbMATH Keywords: word
zbMATH Keywords: square
reviewed by: R. C. Entringer
MaRDI profile type: Publication
OpenAlex ID: W2036042874
cites work: An optimal algorithm for computing the repetitions in a word
cites work: Q4849531
cites work: Squares, cubes, and time-space efficient string searching
cites work: On nonrepetitive sequences
cites work: Uniqueness Theorems for Periodic Functions
cites work: How many squares must a binary sequence contain?
cites work: Corrigendum to: ``The exact number of squares in Fibonacci words''
cites work: Q3659988
DOI: 10.1006/JCTA.1997.2843
Recommended article: How many double squares can a string contain?
Recommended article: How many runs can a string contain?
Recommended article: How many squares must a binary sequence contain?
Recommended article: How many square occurrences must a binary sequence contain?
Recommended article: Learning Theory and Kernel Machines
Recommended article: How many strings are easy to predict?
Recommended article: How Many Magic Squares Are There?
Recommended article: Q4309109
description: scientific article; zbMATH DE number 1212932