Algorithms for jumbled pattern matching in strings

DOI10.1142/S0129054112400175MaRDI QIDQ2909200zbMATH OpenFDO

Authors Péter Burcsi, Ferdinando Cicalese, Gabriele Fici, Zsuzsanna Lipták

Publication date 30 August 2012

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054112400175

zbMATH Keywords

average case analysisParikh vectorspattern matchingpermuted stringsstring algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics on words (68R15) Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• On approximate jumbled pattern matching in strings
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• New algorithms for binary jumbled pattern matching
• On hardness of jumbled indexing
• Efficient indexes for jumbled pattern matching with constant-sized alphabet

Cites work

• A fast string searching algorithm
• Algorithmic complexity of protein identification: Combinatorics of weighted strings
• Efficient text fingerprinting via Parikh mapping
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Scaled and permuted string matching
• The Boyer–Moore–Galil String Searching Strategies Revisited

Cited in

(34)

• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• Finding patterns and periods in Cartesian tree matching
• Fast algorithms for single and multiple pattern Cartesian tree matching
• Improved online algorithms for jumbled matching
• The graph motif problem parameterized by the structure of the input graph
• Binary jumbled string matching for highly run-length compressible texts
• Abelian borders in binary words
• Computing abelian complexity of binary uniform morphic words
• Subquadratic-time algorithms for abelian stringology problems
• Binary jumbled pattern matching on trees and tree-like structures
• Permuted scaled matching
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Algorithms for String Pattern Discovery
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• scientific article; zbMATH DE number 872102 (Why is no real title available?)
• Algorithms for computing abelian periods of words
• Dyck words, lattice paths, and abelian borders
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Cartesian Tree Matching and Indexing
• On hardness of jumbled indexing
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Circular sequence comparison with q-grams
• On infinite prefix normal words
• Bubble-flip -- a new generation algorithm for prefix normal words
• Dyck Words, Lattice Paths, and Abelian Borders
• Fast Cartesian tree matching
• On the complexity of indeterminate strings matching
• Jumbled scattered factors
• Weighted prefix normal words
• On approximate jumbled pattern matching in strings
• Word chain generators for prefix normal words
• On prefix normal words and prefix normal forms
• Weighted prefix normal words: mind the gap
• Binary jumbled pattern matching on trees and tree-like structures

This page was built for publication: Algorithms for jumbled pattern matching in strings

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