Internal dictionary matching

DOI10.1007/s00453-021-00821-yOpenAlexW2991483459MaRDI QIDQ2037109

Panagiotis Charalampopoulos, Wojciech Rytter, Tomasz Kociumaka, Jakub Radoszewski, Manal Mohamed, Tomasz Walen

Publication date: 30 June 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

range searchingdictionary matchingdynamic dictionaryinternal pattern matching

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items

Internal shortest absent word queries in constant time and linear space, Finding top-\(k\) longest palindromes in substrings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• Fast construction of wavelet trees
• Extracting powers and periods in a word from its runs structure
• Space efficient data structures for dynamic orthogonal range counting
• Counting distinct palindromes in a word in linear time
• The level ancestor problem simplified
• Dynamic dictionary matching
• The nearest colored node in a tree
• Improved dynamic dictionary matching
• Generalized substring compression
• Rank and select revisited and extended
• Faster Fully Compressed Pattern Matching by Recompression
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Dynamic text and static pattern matching
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Unifying the Landscape of Cell-Probe Lower Bounds
• Recompression
• Fast Algorithms for Finding Nearest Common Ancestors
• Dictionary matching and indexing with errors and don't cares
• Efficient string matching
• A Linear-Time Algorithm for Seeds Computation
• Longest Common Extensions with Recompression.
• Counting Palindromes in Substrings
• Uniqueness Theorems for Periodic Functions
• The “Runs” Theorem
• Internal Pattern Matching Queries in a Text and Applications
• Wavelet Trees Meet Suffix Trees
• Algorithms on Strings
• On the sorting-complexity of suffix tree construction
• Lowest common ancestors in trees and directed acyclic graphs