Internal dictionary matching

DOI10.1007/S00453-021-00821-YMaRDI QIDQ2037109zbMATH OpenOpenAlexFDO

Authors Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 30 June 2021

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.11577, https://drops.dagstuhl.de/opus/volltexte/2019/11518/

zbMATH Keywords

dictionary matchingdynamic dictionaryinternal pattern matchingrange searching

Mathematics Subject Classification ID

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

Recommendations

• Internal pattern matching queries in a text and applications
• Dynamic dictionary matching in external memory
• Efficient dynamic dictionary matching with DAWGs and AC-automata
• Succinct Dictionary Matching with No Slowdown
• Faster compressed dictionary matching

Cites work

• Algorithms on Strings
• Computing all distinct squares in linear time for integer alphabets
• Counting distinct palindromes in a word in linear time
• Counting distinct patterns in internal dictionary matching
• Counting palindromes in substrings
• Dictionary matching and indexing with errors and don't cares
• Dynamic dictionary matching
• Dynamic dictionary matching and compressed suffix trees
• Dynamic text and static pattern matching
• Efficient string matching
• Extracting powers and periods in a word from its runs structure
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast construction of wavelet trees
• Generalized substring compression
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• Improved dynamic dictionary matching
• Internal dictionary matching
• Internal pattern matching queries in a text and applications
• Longest common extensions with recompression
• Lowest common ancestors in trees and directed acyclic graphs
• Multidimensional divide-and-conquer
• On the sorting-complexity of suffix tree construction
• Rank and select revisited and extended
• Recompression: a simple and powerful technique for word equations
• Space efficient data structures for dynamic orthogonal range counting
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• The ``runs theorem
• The level ancestor problem simplified
• The nearest colored node in a tree
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• Unifying the landscape of cell-probe lower bounds
• Uniqueness Theorems for Periodic Functions
• Wavelet trees meet suffix trees

Cited in

(12)

• Internal shortest absent word queries in constant time and linear space
• scientific article; zbMATH DE number 3866463 (Why is no real title available?)
• Internal pattern matching queries in a text and applications
• Counting distinct patterns in internal dictionary matching
• Internal dictionary matching
• Internal Quasiperiod Queries
• Internal pattern matching queries in a text and applications
• Sorting circular suffixes in linear time
• Internal pattern matching in small space and applications
• Size-constrained weighted ancestors with applications
• Approximate suffix-prefix dictionary queries
• Improved circular dictionary matching

This page was built for publication: Internal dictionary matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037109)