Upper and Lower Bounds for Dynamic Data Structures on Strings

DOI10.4230/LIPIcs.STACS.2018.22zbMath1487.68083arXiv1802.06545OpenAlexW2963160158MaRDI QIDQ3304117

Allan Grønlund, Tatiana Starikovskaya, Kasper Green Larsen, Raphaël Clifford

Publication date: 5 August 2020

Full work available at URL: https://arxiv.org/abs/1802.06545

zbMATH Keywords

inner productHamming distanceconditional lower boundsexact pattern matching with wildcards

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items

Range updates and range sum queries on multidimensional points with monoid weights ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ Dynamic and internal longest common substring ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Longest common substring made fully dynamic

Cites Work

• Unnamed Item
• Unnamed Item
• A black box for online approximate pattern matching
• Approximate string matching using compressed suffix arrays
• Simple deterministic wildcard matching
• Fast algorithms for approximately counting mismatches
• Dictionary matching with a few gaps
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Dynamic text and static pattern matching
• Sparser Johnson-Lindenstrauss Transforms
• Verifying candidate matches in sparse and wildcard matching
• Dictionary matching and indexing with errors and don't cares
• Generalized String Matching
• Text Indexing and Dictionary Matching with One Error
• Faster Online Matrix-Vector Multiplication
• Consequences of Faster Alignment of Sequences
• Indexing methods for approximate dictionary searching
• The cell probe complexity of dynamic range counting

This page was built for publication: Upper and Lower Bounds for Dynamic Data Structures on Strings