Repetitions in strings: algorithms and combinatorics
From MaRDI portal
Publication:1034529
DOI10.1016/j.tcs.2009.08.024zbMath1180.68206OpenAlexW1992151876WikidataQ61677915 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
Related Items
Prefix frequency of lost positions, Square-free words with one possible mismatch, Maximum number of distinct and nonequivalent nonstandard squares in a word, Abelian Repetitions in Sturmian Words, Algorithms for anti-powers in strings, 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, Computing Primitively-Rooted Squares and Runs in Partial Words, Extracting powers and periods in a word from its runs structure, Versatile string kernels, Constructing Words with High Distinct Square Densities, Two-dimensional Fibonacci words: tandem repeats and factor complexity, Towards a Solution to the “Runs” Conjecture, The “Runs” Theorem, Efficient algorithms for shortest partial seeds in words, Unnamed Item, Double string tandem repeats, On the maximal sum of exponents of runs in a string, Partial words with a unique position starting a square, On the Maximal Sum of Exponents of Runsin 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, Efficient counting of square substrings in a tree, The maximal number of cubic runs in a word, The ``runs conjecture, Existence of words over three-letter alphabet not containing squares with replacement errors, Nonrepetitive and pattern-free colorings of the plane, Detecting regularities on grammar-compressed strings, 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
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
