Almost linear time computation of maximal repetitions in run length encoded strings

DOI10.4230/LIPICS.ISAAC.2017.33zbMATH Open1457.68334OpenAlexW2784109755MaRDI QIDQ5136252FDOQ5136252

Authors: Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda 

Publication date: 25 November 2020

Full work available at URL: http://dblp.uni-trier.de/db/conf/isaac/isaac2017.html#FujishigeNIBT17

Recommendations

• Maximal repetitions in strings
• Fast and Practical Algorithms for Computing All the Runs in a String
• Analysis of Maximal Repetitions in Strings
• Space efficient search for maximal repetitions
• scientific article; zbMATH DE number 2051171

zbMATH Keywords

run-length encodingmaximal repetitions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Cites Work

• Factorizing words over an ordered alphabet
• A universal algorithm for sequential data compression
• Title not available (Why is that?)
• On Burnside's Problem
• Free differential calculus. IV: The quotient groups of the lower central series
• Title not available (Why is that?)
• Lempel-Ziv Factorization May Be Harder Than Computing All Runs
• Computing runs on a general alphabet
• An O(n log n) algorithm for finding all repetitions in a string
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• The “Runs” Theorem
• Detecting leftmost maximal periodicities
• Computing longest previous factor in linear time and applications
• Efficient retrieval of approximate palindromes in a run-length encoded string
• A new characterization of maximal repetitions by Lyndon trees
• Faster Compact On-Line Lempel-Ziv Factorization
• Faster Longest Common Extension Queries in Strings over General Alphabets
• The standard factorization of Lyndon words: an average point of view
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Efficient enumeration of non-equivalent squares in partial words with few holes
• Faster STR-IC-LCS Computation via RLE

Cited In (11)

• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• Upper bounds on distinct maximal (sub-)repetitions in compressed strings
• Title not available (Why is that?)
• Crochemore's repetitions algorithm revisited: computing runs
• Space efficient search for maximal repetitions
• Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets
• Hardness of comparing two run-length encoded strings
• Reversal distance for strings with duplicates: linear time approximation using hitting set
• Alphabet-independent algorithms for finding context-sensitive repeats in linear time
• Understanding maximal repetitions in strings
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

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)