Maximal repetitions in strings

DOI10.1016/j.jcss.2007.09.003zbMath1149.68066OpenAlexW2014277465WikidataQ61677921 ScholiaQ61677921MaRDI QIDQ931723

Maxime Crochemore, Lucian Ilie

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.09.003

zbMATH Keywords

combinatorics on wordsrunsmaximal periodicitiesrepetitions in stringsmaximal repetitionssum of exponents

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics on words (68R15)

Related Items

Prefix frequency of lost positions, Upper bounds on distinct maximal (sub-)repetitions in compressed strings, ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS, CROCHEMORE'S REPETITIONS ALGORITHM REVISITED: COMPUTING RUNS, Lower bounds for the number of repetitions in 2D strings, Distinct squares in run-length encoded strings, Computing primitively-rooted squares and runs in partial words, The total run length of a word, A computational framework for determining run-maximal strings, On the structure of run-maximal strings, The three squares lemma revisited, Computing maximal-exponent factors in an overlap-free word, The “Runs” Theorem, Unnamed Item, On the maximal sum of exponents of runs in a string, Not So Many Runs in Strings, Inclusion problems in trace monoids, How many runs can a string contain?, On the Maximal Sum of Exponents of Runsin a String, On the density of Lyndon roots in factors, Bannai et al. method proves the \(d\)-step conjecture for strings, The maximal number of cubic runs in a word, Computing regularities in strings: a survey, On the maximum number of cubic subwords in a word, The ``runs conjecture, Optimal bounds for computing \({\alpha}\)-gapped repeats, Some results on the number of periodic factors in words, A Series of Run-Rich Strings, On primary and secondary repetitions in words, Repetitions in strings: algorithms and combinatorics, Asymptotic behavior of the numbers of runs and microruns, Three overlapping squares: the general case characterized \& applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• How many runs can a string contain?
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• How many squares can a string contain?
• A characterization of the squares in a Fibonacci string
• Detecting leftmost maximal periodicities
• Squares, cubes, and time-space efficient string searching
• 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
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound