Compressed dictionary matching on run-length encoded strings

DOI10.1007/S00453-026-01398-0MaRDI QIDQ7268441zbMATH OpenFDO

Authors Philip Bille, Inge Li Gørtz, Simon J. Puglisi, Simon Rumle Tarnow

Publication date 17 June 2026

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-026-01398-0

zbMATH Keywords

compressed pattern matchingdictionary matchingrun-length encoding

Mathematics Subject Classification ID

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

Cites work

• A framework for dynamic parameterized dictionary matching
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Compressed automata for dictionary matching
• Computing on a free tree via complexity-preserving mappings
• Computing the longest common subsequence of two run-length encoded strings
• Constructing Efficient Dictionaries in Close to Sorting Time
• Deterministic sorting in O(nloglogn) time and linear space
• Dictionary matching and indexing with errors and don't cares
• Dictionary matching in a stream
• Dictionary matching with a few gaps
• Dictionary matching with one gap
• Dynamic dictionary matching
• Dynamic dictionary matching in external memory
• Efficient dynamic method-lookup for object oriented languages
• Efficient string matching
• Fast circular dictionary-matching algorithm
• Fast Pattern Matching in Strings
• Faster algorithms for string matching with k mismatches
• Faster compressed dictionary matching
• Finding level-ancestors in trees
• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• scientific article; zbMATH DE number 140460 (Why is no real title available?)
• scientific article; zbMATH DE number 177536 (Why is no real title available?)
• scientific article; zbMATH DE number 3633757 (Why is no real title available?)
• scientific article; zbMATH DE number 871898 (Why is no real title available?)
• Improved dynamic dictionary matching
• Inplace run-length 2d compressed search.
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Marked ancestor problems
• Matching for run-length encoded strings
• Mind the gap!
• Optimal Two-Dimensional Compressed Matching
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Regular expression matching with multi-strings and intervals
• String matching with variable length gaps
• Sublinear approximate string matching and biological applications
• Succinct Dictionary Matching with No Slowdown
• Succinct online dictionary matching with improved worst-case guarantees
• Which regular expression patterns are hard to match?
• Worst-case efficient single and multiple string matching on packed texts in the word-RAM model

This page was built for publication: Compressed dictionary matching on run-length encoded strings

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