A theory of parameterized pattern matching

DOI10.1145/167088.167115zbMath1310.68098MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68W32: Algorithms on strings

Related Items

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