A \(d\)-step approach to the maximum number of distinct squares and runs in strings

DOI10.1016/J.DAM.2013.10.021zbMath1329.68311OpenAlexW1969844667MaRDI QIDQ496539

Frantisek Franek, Antoine Deza

Publication date: 22 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.10.021

zbMATH Keywords

\((d,n)\)-parameterization\(d\)-step approach

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (8)

A computational substantiation of the \(d\)-step approach to the number of distinct squares problem ⋮ Constructing Words with High Distinct Square Densities ⋮ The “Runs” Theorem ⋮ How many double squares can a string contain? ⋮ On the density of Lyndon roots in factors ⋮ A d-Step Approach for Distinct Squares in Strings ⋮ Bannai et al. method proves the \(d\)-step conjecture for strings ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats

Cites Work

• A computational framework for determining run-maximal strings
• On the structure of run-maximal strings
• A counterexample to the Hirsch conjecture
• The ``runs conjecture
• A continuous \(d\)-step conjecture for polytopes
• How many squares can a string contain?
• A characterization of the squares in a Fibonacci string
• On the maximum number of cubic subwords in a word
• Detecting leftmost maximal periodicities
• Squares, cubes, and time-space efficient string searching
• A note on the number of squares in a word
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• A d-Step Approach for Distinct Squares in Strings

This page was built for publication: A \(d\)-step approach to the maximum number of distinct squares and runs in strings