Repetitions in strings: algorithms and combinatorics

DOI10.1016/j.tcs.2009.08.024zbMath1180.68206WikidataQ61677915 ScholiaQ61677915MaRDI QIDQ1034529

Wojciech Rytter, Lucian Ilie, Maxime Crochemore

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

algorithms; cubes; compression; squares; factorisation; repetitions; tandem repeats; runs; consecutive repeats

Mathematics Subject Classification ID

68R15: Combinatorics on words

Related Items

Unnamed Item, Constructing Words with High Distinct Square Densities, Abelian Repetitions in Sturmian Words, The “Runs” Theorem, Nonrepetitive and pattern-free colorings of the plane, Two-dimensional Fibonacci words: tandem repeats and factor complexity, Square-free words with one possible mismatch, Maximum number of distinct and nonequivalent nonstandard squares in a word, Extracting powers and periods in a word from its runs structure, Versatile string kernels, On the maximal sum of exponents of runs in a string, Fast algorithm for partial covers in words, New simple efficient algorithms computing powers and runs in strings, Average number of occurrences of repetitions in a necklace, The ``runs conjecture, Algorithms for anti-powers in strings, Computing primitively-rooted squares and runs in partial words, Efficient algorithms for shortest partial seeds in words, Partial words with a unique position starting a square, The maximal number of cubic runs in a word, Existence of words over three-letter alphabet not containing squares with replacement errors, Efficient counting of square substrings in a tree, Generating all minimal Petri net unsolvable binary words, Two-dimensional maximal repetitions, DNA combinatorial messages and epigenomics: the case of chromatin organization and nucleosome occupancy in eukaryotic genomes, Existence of words over a binary alphabet free from squares with mismatches, Squares and primitivity in partial words, Prefix frequency of lost positions, Detecting regularities on grammar-compressed strings, Double string tandem repeats, The marble frieze patterns of the cathedral of Siena: geometric structure, multi-stable perception and types of repetition, Computing Primitively-Rooted Squares and Runs in Partial Words, On the Maximal Sum of Exponents of Runsin a String, Towards a Solution to the “Runs” Conjecture

Cites Work

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