How many squares can a string contain?
From MaRDI portal
Publication:1268630
DOI10.1006/JCTA.1997.2843zbMATH Open0910.05001OpenAlexW2036042874MaRDI QIDQ1268630FDOQ1268630
Authors: Aviezri S. Fraenkel, Jamie Simpson 
Publication date: 18 October 1998
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/23b69598766c833f0c87f420432985b42cf5e60f
Recommendations
- How many double squares can a string contain?
- How many runs can a string contain?
- How many squares must a binary sequence contain?
- How many square occurrences must a binary sequence contain?
- How many strings are easy to predict?
- How many strings are easy to predict?
- How Many Magic Squares Are There?
- scientific article; zbMATH DE number 653237
Permutations, words, matrices (05A05) Other combinatorial number theory (11B75) Combinatorics on words (68R15)
Cites Work
- How many squares must a binary sequence contain?
- An optimal algorithm for computing the repetitions in a word
- Title not available (Why is that?)
- Title not available (Why is that?)
- Uniqueness Theorems for Periodic Functions
- Squares, cubes, and time-space efficient string searching
- On nonrepetitive sequences
- Corrigendum to: ``The exact number of squares in Fibonacci words
Cited In (65)
- Finite and infinite closed-rich words
- A NEW PROOF OF THE THREE-SQUARES LEMMA FOR PARTIAL WORDS WITH ONE HOLE
- The square density of words having a sequence of FS-double squares
- A note on the maximum number of \(k\)-powers in a finite word
- An upper bound of the number of distinct powers in binary words
- Lyndon Words, the Three Squares Lemma, and Primitive Squares
- On longest common property preserved substring queries
- Title not available (Why is that?)
- Title not available (Why is that?)
- New simple efficient algorithms computing powers and runs in strings
- Repetitions in Toeplitz words and the Thue threshold
- Characterization of dense patterns having distinct squares
- Clusters of repetition roots: single chains
- Partial words with a unique position starting a square
- Clusters of repetition roots forming prefix chains
- Words with the Maximum Number of Abelian Squares
- Density of distinct squares in non-primitive words
- On the number of squares in partial words
- Maximal repetitions in strings
- Square network on a word
- On closed-rich words
- The three-squares lemma for partial words with one hole
- String powers in trees
- Optimality of some algorithms to detect quasiperiodicities
- How many squares must a binary sequence contain?
- On the maximal number of cubic subwords in a string
- Asymptotic behaviour of the maximal number of squares in standard Sturmian words
- Linear-time computation of local periods
- On the number of frames in binary words
- Abelian-square-rich words
- Efficient counting of square substrings in a tree
- Bi-immunity over different size alphabets
- Extracting powers and periods in a word from its runs structure
- Palindromic Complexity of Trees
- On the average number of regularities in a word
- The exact number of squares in Fibonacci words
- Simple and flexible detection of contiguous repeats using a suffix tree
- Distinct squares in run-length encoded strings
- A computational substantiation of the \(d\)-step approach to the number of distinct squares problem
- Maximum number of distinct and nonequivalent nonstandard squares in a word
- Lower bounds for the number of repetitions in 2D strings
- How many double squares can a string contain?
- Repetitions in strings: algorithms and combinatorics
- A \(d\)-step approach to the maximum number of distinct squares and runs in strings
- Efficient representation and counting of antipower factors in words
- A note on the number of squares in a partial word with one hole
- The number of positions starting a square in binary words
- On the number of \(k\)-powers in a finite word
- On the Number of Distinct Squares in Finite Sequences: Some Old and New Results
- Square-Density Increasing Mappings
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Constructing Words with High Distinct Square Densities
- Shortest covers of all cyclic shifts of a string
- Efficient enumeration of non-equivalent squares in partial words with few holes
- On a lemma of Crochemore and Rytter
- Fast algorithm for partial covers in words
- A \(d\)-step approach for distinct squares in strings
- On the maximum number of cubic subwords in a word
- A note on the number of squares in a word
- Distinct Squares in Circular Words
- Bannai et al. method proves the \(d\)-step conjecture for strings
- Squares in partial words
- A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
- Abelian combinatorics on words: a survey
- String Powers in Trees
This page was built for publication: How many squares can a string contain?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1268630)
