Dynamic and internal longest common substring
From MaRDI portal
Publication:2211363
DOI10.1007/s00453-020-00744-0zbMath1494.68314OpenAlexW3043437193MaRDI QIDQ2211363
Amihood Amir, Panagiotis Charalampopoulos, Jakub Radoszewski, Solon P. Pissis
Publication date: 11 November 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-020-00744-0
Related Items (7)
The heaviest induced ancestors problem: better data structures and applications ⋮ Shortest unique palindromic substring queries in semi-dynamic settings ⋮ Internal shortest absent word queries in constant time and linear space ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Data structures for computing unique palindromes in static and non-static strings ⋮ Near-optimal quantum algorithms for string problems ⋮ Faster queries for longest substring palindrome after block edit
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- A subquadratic algorithm for minimum palindromic factorization
- Dynamic edit distance table under a general weighted cost function
- Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- On the action of the symmetric group on the free Lie algebra and the partition lattice
- Parallel RAM algorithms for factorizing words
- A data structure for dynamic trees
- Lower bounds for set intersection queries
- Longest common substrings with \(k\) mismatches
- Conditional lower bounds for space/time tradeoffs
- Longest repeats with a block of \(k\) don't cares
- Sublinear Space Algorithms for the Longest Common Substring Problem
- Dynamic text and static pattern matching
- Dynamic Text Indexing under String Updates
- Upper and Lower Bounds for Dynamic Data Structures on Strings
- Fast Lightweight Suffix Array Construction and Checking
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Efficient randomized pattern-matching algorithms
- A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
- Algorithms on Strings, Trees and Sequences
- Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences
- Fast parallel Lyndon factorization with applications
- Optimal On-Line Search and Sublinear Time Update in String Matching
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
- Forty Years of Text Indexing
- Time-Space Trade-Offs for the Longest Common Substring Problem
- Repetition Detection in a Dynamic String
- Longest common substring made fully dynamic
- Faster queries for longest substring palindrome after block edit
- Palindromic length in linear time
- Longest Common Prefixes with k-Mismatches and Applications
- Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
- Longest substring palindrome after edit
- Longest Lyndon Substring After Edit
- The Heaviest Induced Ancestors Problem Revisited
- Longest Common Factor After One Edit Operation
- Computing Palindromic Factorizations and Palindromic Covers On-line
- The “Runs” Theorem
- Internal Pattern Matching Queries in a Text and Applications
- More Applications of the Polynomial Method to Algorithm Design
- A new characterization of maximal repetitions by Lyndon trees
- Longest Common Substring with Approximately k Mismatches
- On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
- Minimal Suffix and Rotation of a Substring in Optimal Time
- Orthogonal range searching on the RAM, revisited
- Distance Oracles beyond the Thorup--Zwick Bound
- Algorithms on Strings
- Lyndon Words and Short Superstrings
- On Burnside's Problem
- Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
- 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: Dynamic and internal longest common substring
