The three squares lemma revisited

DOI10.1016/J.JDA.2011.03.009MaRDI QIDQ414439zbMATH OpenOpenAlexWikidataFDO

Authors Evguenia Kopylova, W. F. Smyth

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

combinatorics on wordsmaximal periodicitiesrepetitionsrunsstring algorithmsthree squares lemma

Mathematics Subject Classification ID

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

Recommendations

• Three overlapping squares: the general case characterized \& applications
• Combinatorial Pattern Matching
• A New Periodicity Lemma
• On a lemma of Crochemore and Rytter
• The three-squares lemma for partial words with one hole

Cites work

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

Cited in

(15)

• Computing regularities in strings: a survey
• The denormalized \(3{\times}3\) lemma
• Three overlapping squares: the general case characterized \& applications
• More results on overlapping squares
• Large-scale detection of repetitions
• The new periodicity lemma revisited
• scientific article; zbMATH DE number 3864532 (Why is no real title available?)
• How many double squares can a string contain?
• On a lemma of Crochemore and Rytter
• Constructing words with high distinct square densities
• Distinct squares in circular words
• Are three squares impossible?
• Density of distinct squares in non-primitive words
• Lyndon Words, the Three Squares Lemma, and Primitive Squares
• The two-square lemma

This page was built for publication: The three squares lemma revisited

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