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

DOI10.1016/J.DAM.2013.10.021zbMATH Open1329.68311OpenAlexW1969844667MaRDI QIDQ496539FDOQ496539

Authors: Antoine Deza, Frantisek Franek 

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

Recommendations

• A computational substantiation of the \(d\)-step approach to the number of distinct squares problem
• A \(d\)-step approach for distinct squares in strings
• scientific article; zbMATH DE number 6316138
• A New Periodicity Lemma
• How many double squares can a string contain?

zbMATH Keywords

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

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

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

Cited In (14)

• Optimal bounds for computing \({\alpha}\)-gapped repeats
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• On the maximal sum of exponents of runs in a string
• Constructing words with high distinct square densities
• Distinct squares in run-length encoded strings
• A computational substantiation of the \(d\)-step approach to the number of distinct squares problem
• A computational framework for determining run-maximal strings
• How many double squares can a string contain?
• A \(d\)-step approach for distinct squares in strings
• The ``runs theorem
• On the density of Lyndon roots in factors
• The number of q-ary words with restrictions on the length of the maximal run
• Bannai et al. method proves the \(d\)-step conjecture for strings
• On the Maximal Sum of Exponents of Runsin a String

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496539)