A theory of parameterized pattern matching

DOI10.1145/167088.167115zbMath1310.68098OpenAlexW2026024229MaRDI QIDQ5248473

Brenda S. Baker

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167115

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items

Position heaps for Cartesian-tree matching on strings and tries, Permuted function matching, Weighted approximate parameterized string matching, On updating suffix tree labels, The structural border array, Variations of the parameterized longest previous factor, \(p\)-suffix sorting as arithmetic coding, Parameterized DAWGs: efficient constructions and bidirectional pattern searches, Compressed parameterized pattern matching, Overlap matching., Computing the parameterized Burrows-Wheeler transform online, On-line construction of parameterized suffix trees for large alphabets, A Filtering Technique for All Pairs Approximate Parameterized String Matching, The parameterized suffix tray, Finding patterns and periods in Cartesian tree matching, Online parameterized dictionary matching with one gap, Parameterized longest previous factor, Order-preserving matching, Fast algorithms for single and multiple pattern Cartesian tree matching, Pattern matching with address errors: rearrangement distances, Parameterized dictionary matching and recognition with one gap, A framework for designing space-efficient dictionaries for parameterized and order-preserving matching, Multiple matching of parameterized patterns, Efficient pattern matching for RNA secondary structures, Generalized function matching, A prefix array for parameterized strings, Pattern matching with pair correlation distance, Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics, Succinct non-overlapping indexing, A brief history of parameterized matching problems, Fast parameterized matching with \(q\)-grams, Cartesian Tree Matching and Indexing, Unnamed Item, Order-preserving pattern matching indeterminate strings, Structural Pattern Matching - Succinctly., Alphabet dependence in parameterized matching, A comparative study of dictionary matching with gaps: limitations, techniques and challenges