The three squares lemma revisited

DOI10.1016/j.jda.2011.03.009zbMath1238.68191OpenAlexW2048425099WikidataQ124957587 ScholiaQ124957587MaRDI QIDQ414439

W. F. Smyth, Evguenia Kopylova

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.03.009

zbMATH Keywords

string algorithmsrepetitionscombinatorics on wordsrunsmaximal periodicitiesthree squares lemma

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items

More results on overlapping squares, The new periodicity lemma revisited, Constructing Words with High Distinct Square Densities, Large-scale detection of repetitions, Density of distinct squares in non-primitive words, How many double squares can a string contain?, Distinct Squares in Circular Words, Computing regularities in strings: a survey, Three overlapping squares: the general case characterized \& applications

Cites Work

• Maximal repetitions in strings
• How many runs can a string contain?
• Computing longest previous factor in linear time and applications
• Intersecting periodic words
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• Detecting leftmost maximal periodicities
• Squares, cubes, and time-space efficient string searching
• An O(n log n) algorithm for finding all repetitions in a string
• Fast and Practical Algorithms for Computing All the Runs in a String
• Towards a Solution to the “Runs” Conjecture
• Not So Many Runs in Strings
• A universal algorithm for sequential data compression
• Uniqueness Theorems for Periodic Functions
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• A New Periodicity Lemma
• Unnamed Item
• Unnamed Item
• Unnamed Item