Breaking a barrier in constructing compact indexes for parameterized pattern matching

DOI10.4230/LIPICS.ICALP.2024.89MaRDI QIDQ6875106zbMATH OpenFDO

Authors Kento Iseri, Tomohiro I, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.89

zbMATH Keywords

index for parameterized pattern matchingonline constructionparameterized Burrows-Wheeler transform

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• p-suffix sorting as arithmetic coding
• A brief history of parameterized matching problems
• A Compact Index for Cartesian Tree Matching
• A theory of parameterized pattern matching
• An encoding for order-preserving matching
• Compressed Data Structures for Dynamic Sequences
• Computing the parameterized Burrows-Wheeler transform online
• Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets
• Dynamic integer sets with optimal rank, select, and predecessor search
• Faster Suffix Tree Construction with Missing Suffix Links
• Fully functional parameterized suffix trees in compact space
• Generalized pattern matching and periodicity under substring consistent equivalence relations
• scientific article; zbMATH DE number 1306895 (Why is no real title available?)
• scientific article; zbMATH DE number 7651154 (Why is no real title available?)
• Lightweight parameterized suffix array construction
• On-line construction of parameterized suffix trees for large alphabets
• PalFM-index: FM-index for palindrome pattern matching
• Parameterized DAWGs: efficient constructions and bidirectional pattern searches
• Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance
• Parameterized pattern matching: Algorithms and applications
• pBWT: achieving succinct data structures for parameterized pattern matching and related problems
• Position heaps for parameterized strings
• Simpler FM-index for parameterized string matching
• Structural Pattern Matching - Succinctly.
• The parameterized position heap of a trie
• The parameterized suffix tray
• The suffix binary search tree and suffix AVL tree
• Wavelet trees for all

Cited in

(3)

• Inverting parameterized Burrows-Wheeler transform
• The ceBWT index: an index for circular Cartesian tree matching on multiple texts
• Extending the Burrows-Wheeler transform for Cartesian tree matching and constructing it

This page was built for publication: Breaking a barrier in constructing compact indexes for parameterized pattern matching

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