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

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

zbMATH Keywords

pattern matchingapproximate searchstring algorithmsaverage case analysisParikh vectorspermuted strings

Mathematics Subject Classification ID

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

Cites Work

• Compressed representations of sequences and full-text indexes
• Fast Pattern Matching in Strings
• Efficient text fingerprinting via Parikh mapping
• Algorithms for jumbled pattern matching in strings
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Title not available (Why is that?)
• Scaled and permuted string matching
• Algorithmic complexity of protein identification: Combinatorics of weighted strings
• Indexing permutations for binary strings
• Necklaces, Convolutions, and X + Y
• A fast and simple algorithm for the money changing problem
• A Stochastic Allocation Problem
• Optimal storage allocation for serial files
• The generalized Banach match-box problem: Application in disc storage management
• Computing rank-convolutions with a mask
• ERRATUM: "INDUCED ELECTROSTATIC SELF-INTERACTION IN THE SPACE–TIME OF A GLOBAL MONOPOLE WITH INNER STRUCTURE"

Cited In (21)

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

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)