How many squares can a string contain?

DOI10.1006/jcta.1997.2843zbMath0910.05001OpenAlexW2036042874MaRDI QIDQ1268630

Aviezri S. Fraenkel, R. 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

zbMATH Keywords

square word

Mathematics Subject Classification ID

Combinatorics on words (68R15) Permutations, words, matrices (05A05) Other combinatorial number theory (11B75)

Related Items

Abelian-square-rich words, Characterization of dense patterns having distinct squares, Clusters of repetition roots: single chains, Words with the Maximum Number of Abelian Squares, Square-Density Increasing Mappings, A note on the number of squares in a word, Palindromic Complexity of Trees, 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, ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS, Lower bounds for the number of repetitions in 2D strings, Distinct squares in run-length encoded strings, String Powers in Trees, String powers in trees, Extracting powers and periods in a word from its runs structure, On the number of \(k\)-powers in a finite word, Constructing Words with High Distinct Square Densities, The square density of words having a sequence of FS-double squares, Abelian combinatorics on words: a survey, On the Number of Distinct Squares in Finite Sequences: Some Old and New Results, Finite and infinite closed-rich words, The three-squares lemma for partial words with one hole, Density of distinct squares in non-primitive words, Unnamed Item, An upper bound of the number of distinct powers in binary words, On the average number of regularities in a word, Squares in partial words, Unnamed Item, How many double squares can a string contain?, Maximal repetitions in strings, Partial words with a unique position starting a square, On a lemma of Crochemore and Rytter, Fast algorithm for partial covers in words, New simple efficient algorithms computing powers and runs in strings, A \(d\)-step approach to the maximum number of distinct squares and runs in strings, Distinct Squares in Circular Words, A d-Step Approach for Distinct Squares in Strings, Bi-immunity over different size alphabets, Square network on a word, Bannai et al. method proves the \(d\)-step conjecture for strings, Efficient counting of square substrings in a tree, On the maximum number of cubic subwords in a word, Linear time algorithms for finding and representing all the tandem repeats in a string, Shortest covers of all cyclic shifts of a string, Linear-time computation of local periods, On the number of squares in partial words, Optimality of some algorithms to detect quasiperiodicities, On the number of frames in binary words, Simple and flexible detection of contiguous repeats using a suffix tree, A NEW PROOF OF THE THREE-SQUARES LEMMA FOR PARTIAL WORDS WITH ONE HOLE, Efficient representation and counting of antipower factors in words, Repetitions in strings: algorithms and combinatorics, A note on the number of squares in a partial word with one hole, The exact number of squares in Fibonacci words, A simple proof that a word of length \(n\) has at most \(2n\) distinct squares, Repetitions in Toeplitz words and the Thue threshold, Clusters of repetition roots forming prefix chains, Efficient enumeration of non-equivalent squares in partial words with few holes, On closed-rich words

Cites Work