Repetitions in strings: algorithms and combinatorics
From MaRDI portal
Publication:1034529
DOI10.1016/J.TCS.2009.08.024zbMATH Open1180.68206OpenAlexW1992151876WikidataQ61677915 ScholiaQ61677915MaRDI QIDQ1034529FDOQ1034529
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
Recommendations
Cites Work
- Two-way string-matching
- Algorithms on Strings, Trees and Sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Jewels of Stringology
- Title not available (Why is that?)
- An optimal algorithm for computing the repetitions in a word
- Optimal off-line detection of repetitions in a string
- Repetitions in the Fibonacci infinite word
- Time-space-optimal string matching
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Squares, cubes, and time-space efficient string searching
- An O(n log n) algorithm for finding all repetitions in a string
- Algorithms on Strings
- How many squares can a string contain?
- Transducers and repetitions
- 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
- Detecting leftmost maximal periodicities
- Fast and Practical Algorithms for Computing All the Runs in a String
- Computing regularities in strings: a survey
- Not So Many Runs in Strings
- The Number of Runs in Sturmian Words
- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
- Maximal repetitions in strings
- How many runs can a string contain?
- Computing longest previous factor in linear time and applications
- The structure of subword graphs and suffix trees of Fibonacci words
- A characterization of the squares in a Fibonacci string
- Repetitive perhaps, but certainly not boring
- Towards a Solution to the “Runs” Conjecture
- AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
- The number of runs in a string
- Analysis of Maximal Repetitions in Strings
- Bounds on Powers in Strings
- Title not available (Why is that?)
- The exact number of squares in Fibonacci words
- Crochemore Factorization of Sturmian and Other Infinite Words
- Repetitions in Sturmian strings
- The Lempel–Ziv Complexity of Fixed Points of Morphisms
- Title not available (Why is that?)
Cited In (45)
- Versatile string kernels
- Are three squares impossible?
- On the maximal sum of exponents of runs in a string
- New simple efficient algorithms computing powers and runs in strings
- The ``runs conjecture
- Constructing words with high distinct square densities
- DNA combinatorial messages and epigenomics: the case of chromatin organization and nucleosome occupancy in eukaryotic genomes
- Clusters of repetition roots: single chains
- 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
- Detecting regularities on grammar-compressed strings
- Efficient counting of square substrings in a tree
- Extracting powers and periods in a word from its runs structure
- 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
- Abelian repetitions in Sturmian words
- On primary and secondary repetitions in 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
- Two-dimensional Fibonacci words: tandem repeats and factor complexity
- Towards a Solution to the “Runs” Conjecture
- A combinatorial view on string attractors
- Nonrepetitive and pattern-free colorings of the plane
- Online algorithms on antipowers and antiperiods
- Double string tandem repeats
- Title not available (Why is that?)
- Computing equality-free and repetitive string factorisations
- On the Maximal Sum of Exponents of Runsin a String
- Efficient algorithms for shortest partial seeds in words
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)
