Repetitions in strings: algorithms and combinatorics

DOI10.1016/J.TCS.2009.08.024MaRDI QIDQ1034529zbMATH OpenOpenAlexWikidataFDO

Authors Maxime Crochemore, Lucian Ilie, Wojciech Rytter

Publication date 6 November 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.08.024

zbMATH Keywords

algorithmscompressionrunscubesrepetitionssquaresfactorisationtandem repeatsconsecutive repeats

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Large-scale detection of repetitions
• The runs theorem and beyond
• Combinatorial Pattern Matching
• Understanding maximal repetitions in strings
• A New Periodicity Lemma

Cites work

• scientific article; zbMATH DE number 3723890 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 2105037 (Why is no real title available?)
• scientific article; zbMATH DE number 756768 (Why is no real title available?)
• A characterization of the squares in a Fibonacci string
• 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
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• An O(n log n) algorithm for finding all repetitions in a string
• An optimal algorithm for computing the repetitions in a word
• Analysis of Maximal Repetitions in Strings
• Bounds on Powers in Strings
• Computing longest previous factor in linear time and applications
• Computing regularities in strings: a survey
• Crochemore Factorization of Sturmian and Other Infinite Words
• Detecting leftmost maximal periodicities
• Fast and Practical Algorithms for Computing All the Runs in a String
• How many runs can a string contain?
• How many squares can a string contain?
• Jewels of Stringology
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Maximal repetitions in strings
• Not So Many Runs in Strings
• Optimal off-line detection of repetitions in a string
• Repetitions in Sturmian strings
• Repetitions in the Fibonacci infinite word
• Repetitive perhaps, but certainly not boring
• Squares, cubes, and time-space efficient string searching
• The Lempel–Ziv Complexity of Fixed Points of Morphisms
• The Number of Runs in Sturmian Words
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• The exact number of squares in Fibonacci words
• The number of runs in a string
• The structure of subword graphs and suffix trees of Fibonacci words
• Time-space-optimal string matching
• Towards a Solution to the “Runs” Conjecture
• Transducers and repetitions
• Two-way string-matching

Cited in

(45)

• Efficient algorithms for shortest partial seeds in words
• On the Maximal Sum of Exponents of Runsin a String
• Versatile string kernels
• On the maximal sum of exponents of runs in a string
• New simple efficient algorithms computing powers and runs in strings
• The ``runs conjecture
• Are three squares impossible?
• Clusters of repetition roots: single chains
• DNA combinatorial messages and epigenomics: the case of chromatin organization and nucleosome occupancy in eukaryotic genomes
• Constructing words with high distinct square densities
• Partial words with a unique position starting a square
• The marble frieze patterns of the cathedral of Siena: geometric structure, multi-stable perception and types of repetition
• The maximal number of cubic runs in a word
• Square-free words with one possible mismatch
• Extracting powers and periods in a word from its runs structure
• Detecting regularities on grammar-compressed strings
• Efficient counting of square substrings in a tree
• Algorithms for anti-powers in strings
• Two-dimensional maximal repetitions
• Repetitive perhaps, but certainly not boring
• Prefix frequency of lost positions
• Maximum number of distinct and nonequivalent nonstandard squares in a word
• Large-scale detection of repetitions
• Squares and primitivity in partial words
• Two-dimensional maximal repetitions
• Generating all minimal Petri net unsolvable binary words
• Existence of words over three-letter alphabet not containing squares with replacement errors
• On primary and secondary repetitions in words
• Abelian repetitions in Sturmian words
• Computing primitively-rooted squares and runs in partial words
• Computing primitively-rooted squares and runs in partial words
• Hunting redundancies in strings
• Fast algorithm for partial covers in words
• Average number of occurrences of repetitions in a necklace
• Exact and inexact search for 2d side-sharing tandems
• Existence of words over a binary alphabet free from squares with mismatches
• The ``runs theorem
• A combinatorial view on string attractors
• Towards a Solution to the “Runs” Conjecture
• Two-dimensional Fibonacci words: tandem repeats and factor complexity
• Nonrepetitive and pattern-free colorings of the plane
• Double string tandem repeats
• Online algorithms on antipowers and antiperiods
• scientific article; zbMATH DE number 3864532 (Why is no real title available?)
• Computing equality-free and repetitive string factorisations

This page was built for publication: Repetitions in strings: algorithms and combinatorics

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