An optimal algorithm for computing the repetitions in a word
From MaRDI portal
Cites work
- Fast Pattern Matching in Strings
- scientific article; zbMATH DE number 3770980 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3350192 (Why is no real title available?)
- Partitioning a graph in \(O(|A|\log_ 2|V|)\)
Cited in
(only showing first 100 items - show all)- Repetitions in strings: algorithms and combinatorics
- Sequences generated by infinitely iterated morphisms
- Structural properties of the string statistics problem
- Optimal off-line detection of repetitions in a string
- Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
- Efficient parallel algorithms to test square-freeness and factorize strings
- Optimal parallel detection of squares in strings
- How many squares can a string contain?
- The exact number of squares in Fibonacci words
- Quasiperiodicity and string covering
- An optimal algorithm to compute all the covers of a string
- A characterization of the squares in a Fibonacci string
- Weak repetitions in Sturmian strings.
- Generalizations of suffix arrays to multi-dimensional matrices.
- Finding approximate repetitions under Hamming distance.
- Fibonacci arrays and their two-dimensional repetitions
- Repetitions in Sturmian strings
- Repetitive perhaps, but certainly not boring
- Computing primitively-rooted squares and runs in partial words
- Searching of gapped repeats and subrepetitions in a word
- Period recovery of strings over the Hamming and edit distances
- On the number of gapped repeats with arbitrary gap
- Crochemore's partitioning on weighted strings and applications
- Computing regularities in strings: a survey
- On the maximum number of cubic subwords in a word
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Detecting leftmost maximal periodicities
- A linear time lower bound on McCreight and general updating algorithms for suffix trees
- Speeding up the detection of evolutive tandem repeats
- Detecting morphic images of a word: On the rank of a pattern
- Covering a string
- Computing all subtree repeats in ordered trees
- Multidimensional period recovery
- On the approximation ratio of LZ-end to LZ77
- Experimental evaluation of algorithms for computing quasiperiods
- Optimal bounds for computing \({\alpha}\)-gapped repeats
- Squares and primitivity in partial words
- Approximate periodicity
- Three overlapping squares: the general case characterized \& applications
- A note on the number of squares in a word
- More results on overlapping squares
- On left and right seeds of a string
- The number of runs in a string
- Computing the \(\lambda \)-covers of a string
- Locating maximal approximate runs in a string
- Closest periodic vectors in \(L_p\) spaces
- Constructing suffix arrays in linear time
- Optimal discovery of repetitions in 2D
- On shuffled-square-free words
- Polynomial time multiplication and normal forms in free bands
- Improved linear systolic algorithms for substring statistics
- Asymptotic behaviour of the maximal number of squares in standard Sturmian words
- Computing primitively-rooted squares and runs in partial words
- Longest -gapped repeat and palindrome
- On prefix/suffix-square free words
- Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
- Polynomial-time approximation algorithms for weighted LCS problem
- scientific article; zbMATH DE number 3864532 (Why is no real title available?)
- ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS
- Optimal Parallel Searching an Array for Certain Repetitions
- Repetitions detection on a linear array with reconfigurable pipelined bus system
- Towards a Solution to the “Runs” Conjecture
- Bounds on Powers in Strings
- NUMBER OF OCCURRENCES OF POWERS IN STRINGS
- Average value of sum of exponents of runs in a string
- Un réseau linéaire pour la reconnaissance des mots sans carré
- The three squares lemma revisited
- Efficient string matching on packed texts
- Detecting the morphic images of a word : improving the general algorithm
- Algorithms For Computing Approximate Repetitions In Musical Sequences
- \(k\)-abelian pattern matching
- New simple efficient algorithms computing powers and runs in strings
- Average number of occurrences of repetitions in a necklace
- Constructing words with high distinct square densities
- Ziv-Lempel and Crochemore factorizations of the generalized period-doubling word
- Repetition Detection in a Dynamic String
- Efficient solving of the word equations in one variable
- Optimal parallel algorithms for periods, palindromes and squares (extended abstract)
- On the prefix-suffix duplication reduction
- Generalized approximate regularities in strings
- New complexity results for the k-covers problem
- WORD COMPLEXITY AND REPETITIONS IN WORDS
- The number of repetitions in 2D-strings
- Efficient Computation of 2-Covers of a String.
- Approximate periods of strings
- Simple and flexible detection of contiguous repeats using a suffix tree
- Generalizations of suffix arrays to multi-dimensional matrices.
- String Covering: A Survey
- The length of the longest sequence of consecutive FS-double squares in a word
- Near-optimal quantum algorithms for string problems
- Optimal bounds for distinct quartics
- Efficient detection of quasiperiodicities in strings
- Linear-time computation of local periods
- On the number of frames in binary words
- Counting distinct square substrings in sublinear time
- On primary and secondary repetitions in words
- A coarse-grained multicomputer algorithm for the detection of repetitions
- A fast algorithm for finding the positions of all squares in a run-length encoded string
- An efficient algorithm for online square detection
- Maximal repetitions in strings
This page was built for publication: An optimal algorithm for computing the repetitions in a word
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1155963)
