On approximate jumbled pattern matching in strings

DOI10.1007/S00224-011-9344-5zbMATH Open1253.68372OpenAlexW2074382201MaRDI QIDQ692932FDOQ692932

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

Publication date 6 December 2012

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-011-9344-5

zbMATH Keywords

pattern matchingapproximate searchstring algorithmsaverage case analysisParikh vectorspermuted strings

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Algorithms on strings (68W32)

Recommendations

• Algorithms for jumbled pattern matching in strings
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Improved online algorithms for jumbled matching
• New algorithms for binary jumbled pattern matching
• Subquadratic-time algorithms for abelian stringology problems

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• A Stochastic Allocation Problem
• A fast and simple algorithm for the money changing problem
• Algorithmic complexity of protein identification: Combinatorics of weighted strings
• Algorithms for jumbled pattern matching in strings
• Compressed representations of sequences and full-text indexes
• Computing rank-convolutions with a mask
• Efficient text fingerprinting via Parikh mapping
• Fast Pattern Matching in Strings
• Indexing permutations for binary strings
• Necklaces, Convolutions, and X + Y
• Optimal storage allocation for serial files
• Scaled and permuted string matching
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• The generalized Banach match-box problem: Application in disc storage management

Cited in

(21)

• Computing abelian complexity of binary uniform morphic words
• Algorithms for computing abelian periods of words
• Dyck Words, Lattice Paths, and Abelian Borders
• Algorithms for jumbled pattern matching in strings
• Cartesian Tree Matching and Indexing
• Finding patterns and periods in Cartesian tree matching
• Improved online algorithms for jumbled matching
• scientific article; zbMATH DE number 7651042 (Why is no real title available?)
• On prefix normal words and prefix normal forms
• Binary jumbled pattern matching on trees and tree-like structures
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Approximating the maximum consecutive subsums of a sequence
• On infinite prefix normal words
• On the relationship between histogram indexing and block-mass indexing
• Permuted scaled matching
• Binary jumbled string matching for highly run-length compressible texts
• scientific article; zbMATH DE number 2081034 (Why is no real title available?)
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• Dyck words, lattice paths, and abelian borders

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

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