Almost linear time computation of maximal repetitions in run length encoded strings
From MaRDI portal
Recommendations
Cites work
- A fully compressed algorithm for computing the edit distance of run-length encoded strings
- A new characterization of maximal repetitions by Lyndon trees
- A universal algorithm for sequential data compression
- An O(n log n) algorithm for finding all repetitions in a string
- Computing longest previous factor in linear time and applications
- Computing runs on a general alphabet
- Detecting leftmost maximal periodicities
- Efficient enumeration of non-equivalent squares in partial words with few holes
- Efficient retrieval of approximate palindromes in a run-length encoded string
- Factorizing words over an ordered alphabet
- Faster compact on-line Lempel-Ziv factorization
- Faster longest common extension queries in strings over general alphabets
- Faster STR-IC-LCS computation via RLE
- Free differential calculus. IV: The quotient groups of the lower central series
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 1390079 (Why is no real title available?)
- Lempel-Ziv factorization may be harder than computing all runs
- On Burnside's Problem
- The ``runs theorem
- The standard factorization of Lyndon words: an average point of view
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
Cited in
(14)- Reversal distance for strings with duplicates: linear time approximation using hitting set
- Tighter bounds and optimal algorithms for all maximal -gapped repeats and palindromes. Finding all maximal -gapped repeats and palindromes in optimal worst case time on integer alphabets
- Crochemore's repetitions algorithm revisited: computing runs
- Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
- scientific article; zbMATH DE number 2051171 (Why is no real title available?)
- Understanding maximal repetitions in strings
- Alphabet-independent algorithms for finding context-sensitive repeats in linear time
- On maximal repeats in compressed strings
- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
- Space efficient search for maximal repetitions
- On the compressiveness of the Burrows-Wheeler transform
- Upper bounds on distinct maximal (sub-)repetitions in compressed strings
- Computing runs on a general alphabet
- Hardness of comparing two run-length encoded strings
This page was built for publication: Almost linear time computation of maximal repetitions in run length encoded strings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136252)
