Longest common substring made fully dynamic
From MaRDI portal
Publication:5075739
DOI10.4230/LIPIcs.ESA.2019.6OpenAlexW2978042462MaRDI QIDQ5075739
Amihood Amir, Solon P. Pissis, Panagiotis Charalampopoulos, Jakub Radoszewski
Publication date: 11 May 2022
Full work available at URL: https://arxiv.org/abs/1804.08731
Related Items
Minimal unique palindromic substrings after single-character substitution, The heaviest induced ancestors problem: better data structures and applications, Near-optimal quantum algorithms for string problems, Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems, Dynamic and internal longest common substring, Repetition Detection in a Dynamic String, Longest property-preserved common factor: a new string-processing framework
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- Simple deterministic wildcard matching
- On the action of the symmetric group on the free Lie algebra and the partition lattice
- Which problems have strongly exponential complexity?
- A data structure for dynamic trees
- Longest common substrings with \(k\) mismatches
- Longest common substring with approximately \(k\) mismatches
- Longest repeats with a block of \(k\) don't cares
- Sublinear Space Algorithms for the Longest Common Substring Problem
- Dynamic Text Indexing under String Updates
- Upper and Lower Bounds for Dynamic Data Structures on Strings
- Fast Lightweight Suffix Array Construction and Checking
- Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences
- Optimal On-Line Search and Sublinear Time Update in String Matching
- Faster algorithms for string matching with k mismatches
- Forty Years of Text Indexing
- Time-Space Trade-Offs for the Longest Common Substring Problem
- Repetition Detection in a Dynamic String
- 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
- Linear-Time Algorithm for Long LCF with k Mismatches
- Longest Common Factor After One Edit Operation
- Consequences of Faster Alignment of Sequences
- Internal Pattern Matching Queries in a Text and Applications
- More Applications of the Polynomial Method to Algorithm Design
- Longest Common Substring with Approximately k Mismatches
- On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
- Algorithms on Strings
- On Burnside's Problem
- Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
- On the complexity of \(k\)-SAT
- Longest common prefixes with \(k\)-errors and applications