Repetition Detection in a Dynamic String

DOI10.4230/LIPIcs.ESA.2019.5OpenAlexW2978939959MaRDI QIDQ5075738

Itai Boneh, Eitan Kondratovsky, Panagiotis Charalampopoulos, Amihood Amir

Publication date: 11 May 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11126/pdf/LIPIcs-ESA-2019-5.pdf/

zbMATH Keywords

squaresdynamic algorithmsstring algorithmsrepetitionsruns

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (12)

Multidimensional period recovery ⋮ Minimal unique palindromic substrings after single-character substitution ⋮ The heaviest induced ancestors problem: better data structures and applications ⋮ Shortest unique palindromic substring queries in semi-dynamic settings ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Data structures for computing unique palindromes in static and non-static strings ⋮ Unnamed Item ⋮ Near-optimal quantum algorithms for string problems ⋮ Unnamed Item ⋮ Dynamic and internal longest common substring ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Longest common substring made fully dynamic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extracting powers and periods in a word from its runs structure
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• Dynamic dictionary matching in external memory
• Dynamic dictionary matching with failure functions
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Improved dynamic dictionary matching
• Dynamic text and static pattern matching
• Dynamic Text Indexing under String Updates
• An O(n log n) algorithm for finding all repetitions in a string
• Efficient randomized pattern-matching algorithms
• Dynamic Orthogonal Range Searching on the RAM, Revisited
• Longest common substring made fully dynamic
• Faster queries for longest substring palindrome after block edit
• Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
• Longest substring palindrome after edit
• The Heaviest Induced Ancestors Problem Revisited
• Longest Common Factor After One Edit Operation
• Uniqueness Theorems for Periodic Functions
• The “Runs” Theorem
• Internal Pattern Matching Queries in a Text and Applications
• Algorithms on Strings

This page was built for publication: Repetition Detection in a Dynamic String