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)

zbMATH Keywords

pattern matchingstring algorithmsaverage case analysisParikh vectorspermuted strings

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• 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
• Scaled and permuted string matching
• The Boyer–Moore–Galil String Searching Strategies Revisited

Cited in

(30)

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

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)