pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems

DOI10.1137/1.9781611974782.25zbMath1410.68098OpenAlexW4252347333MaRDI QIDQ4575762

Sharma V. Thankachan, Rahul Shah, Arnab Ganguly

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.25

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)

Related Items (12)

Wheeler graphs: a framework for BWT-based data structures ⋮ Parameterized DAWGs: efficient constructions and bidirectional pattern searches ⋮ Computing the parameterized Burrows-Wheeler transform online ⋮ The parameterized suffix tray ⋮ A framework for designing space-efficient dictionaries for parameterized and order-preserving matching ⋮ Simpler FM-index for parameterized string matching ⋮ Succinct non-overlapping indexing ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ A brief history of parameterized matching problems ⋮ An Encoding for Order-Preserving Matching. ⋮ Structural Pattern Matching - Succinctly. ⋮ On the complexity of recognizing Wheeler graphs

Uses Software

• CLICS

This page was built for publication: pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems