Repetitions in strings: algorithms and combinatorics
From MaRDI portal
Publication:1034529
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
algorithms; cubes; compression; squares; factorisation; repetitions; tandem repeats; runs; consecutive repeats
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