Longest common substring made fully dynamic
From MaRDI portal
Recommendations
- Dynamic and internal longest common substring
- Locally maximal common factors as a tool for efficient dynamic string algorithms
- Longest common factor after one edit operation
- A fast longest common subsequence algorithm for similar strings
- Fully dynamic data structure for LCE queries in compressed space
Cites work
- A data structure for dynamic trees
- Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
- Algorithms on Strings
- Consequences of Faster Alignment of Sequences
- Dynamic Text Indexing under String Updates
- Fast lightweight suffix array construction and checking
- Faster algorithms for string matching with k mismatches
- Faster queries for longest substring palindrome after block edit
- Forty Years of Text Indexing
- scientific article; zbMATH DE number 1003303 (Why is no real title available?)
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- scientific article; zbMATH DE number 6850408 (Why is no real title available?)
- scientific article; zbMATH DE number 1445383 (Why is no real title available?)
- Internal pattern matching queries in a text and applications
- Linear-time algorithm for long LCF with k mismatches
- Locally maximal common factors as a tool for efficient dynamic string algorithms
- Longest common factor after one edit operation
- Longest common prefixes with k-errors and applications
- Longest common substring with approximately \(k\) mismatches
- Longest common substring with approximately \(k\) mismatches
- Longest common substrings with k mismatches
- Longest repeats with a block of \(k\) don't cares
- Longest substring palindrome after edit
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- More applications of the polynomial method to algorithm design
- On Burnside's Problem
- On the action of the symmetric group on the free Lie algebra and the partition lattice
- On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
- On the complexity of k-SAT
- Optimal On-Line Search and Sublinear Time Update in String Matching
- Repetition Detection in a Dynamic String
- Simple deterministic wildcard matching
- Sublinear space algorithms for the longest common substring problem
- The heaviest induced ancestors problem revisited
- Time-space trade-offs for the longest common substring problem
- Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences
- Upper and lower bounds for dynamic data structures on strings
- Which problems have strongly exponential complexity?
Cited in
(10)- Minimal unique palindromic substrings after single-character substitution
- The heaviest induced ancestors problem: better data structures and applications
- Dynamic and internal longest common substring
- Longest property-preserved common factor: a new string-processing framework
- Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
- Repetition Detection in a Dynamic String
- Longest Lyndon Substring After Edit
- Near-optimal quantum algorithms for string problems
- Dynamic longest common substring in polylogarithmic time
- Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
This page was built for publication: Longest common substring made fully dynamic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075739)
