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

DOI10.4230/LIPIcs.ISAAC.2017.33zbMath1457.68334OpenAlexW2784109755MaRDI QIDQ5136252

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

Publication date: 25 November 2020

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

zbMATH Keywords

run-length encodingmaximal repetitions

Mathematics Subject Classification ID

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

Cites Work

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

This page was built for publication: Almost linear time computation of maximal repetitions in run length encoded strings