Constructing words with high distinct square densities
From MaRDI portal
(Redirected from Publication:5016360)
Abstract: Fraenkel and Simpson showed that the number of distinct squares in a word of length n is bounded from above by 2n, since at most two distinct squares have their rightmost, or last, occurrence begin at each position. Improvements by Ilie to and by Deza et al. to 11n/6 rely on the study of combinatorics of FS-double-squares, when the maximum number of two last occurrences of squares begin. In this paper, we first study how to maximize runs of FS-double-squares in the prefix of a word. We show that for a given positive integer m, the minimum length of a word beginning with m FS-double-squares, whose lengths are equal, is 7m+3. We construct such a word and analyze its distinct-square-sequence as well as its distinct-square-density. We then generalize our construction. We also construct words with high distinct-square-densities that approach 5/6.
Recommendations
Cites work
- A d-step approach to the maximum number of distinct squares and runs in strings
- A New Periodicity Lemma
- A note on the number of squares in a partial word with one hole
- 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 stronger square conjecture on binary words
- Algorithms on Strings
- Algorithms on Strings, Trees and Sequences
- An O(n log n) algorithm for finding all repetitions in a string
- An optimal algorithm for computing the repetitions in a word
- Compression of individual sequences via variable-rate coding
- Computing primitively-rooted squares and runs in partial words
- Computing primitively-rooted squares and runs in partial words
- Counting distinct squares in partial words
- Extracting powers and periods in a word from its runs structure
- How many double squares can a string contain?
- How many square occurrences must a binary sequence contain?
- How many squares can a string contain?
- How many squares must a binary sequence contain?
- scientific article; zbMATH DE number 1024080 (Why is no real title available?)
- scientific article; zbMATH DE number 1557065 (Why is no real title available?)
- scientific article; zbMATH DE number 2183071 (Why is no real title available?)
- Jewels of Stringology
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word
- More results on overlapping squares
- On the maximum number of cubic subwords in a word
- On the number of squares in partial words
- Optimal off-line detection of repetitions in a string
- Repetitions in strings: algorithms and combinatorics
- Square-density increasing mappings
- Squares and primitivity in partial words
- Squares in partial words
- Squares, cubes, and time-space efficient string searching
- The number of positions starting a square in binary words
- The three squares lemma revisited
- The three-squares lemma for partial words with one hole
- Two-way string-matching
Cited in
(7)- Square network on a word
- Square-density increasing mappings
- Generating square-free words efficiently
- Effective designs based on individual word length patterns
- The square density of words having a sequence of FS-double squares
- The length of the longest sequence of consecutive FS-double squares in a word
- Characterization of dense patterns having distinct squares
This page was built for publication: Constructing words with high distinct square densities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5016360)
